{"id":1970,"date":"2018-03-05T20:22:58","date_gmt":"2018-03-06T04:22:58","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=1970"},"modified":"2018-03-05T20:41:57","modified_gmt":"2018-03-06T04:41:57","slug":"leetcode-496-next-greater-element-i","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/array\/leetcode-496-next-greater-element-i\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 496. Next Greater Element I"},"content":{"rendered":"
\n

\u9898\u76ee\u5927\u610f\uff1a\u7ed9\u4f60\u4e00\u4e2a\u7ec4\u6570A\u91cc\u9762\u6bcf\u4e2a\u5143\u7d20\u90fd\u4e0d\u76f8\u540c\u3002\u518d\u7ed9\u4f60\u4e00\u4e2a\u6570\u7ec4B\uff0c\u5143\u7d20\u662fA\u7684\u5b50\u96c6\uff0c\u95ee\u5bf9\u4e8eB\u4e2d\u7684\u6bcf\u4e2a\u5143\u7d20\uff0c\u5728A\u6570\u7ec4\u4e2d\u76f8\u540c\u5143\u7d20\u4e4b\u540e\u7b2c\u4e00\u4e2a\u6bd4\u5b83\u7684\u5143\u7d20\u662f\u591a\u5c11\u3002<\/p>\n

Problem:<\/strong><\/p>\n

You are given two arrays\u00a0(without duplicates)<\/b>\u00a0nums1<\/code>\u00a0and\u00a0nums2<\/code>\u00a0where\u00a0nums1<\/code>\u2019s elements are subset of\u00a0nums2<\/code>. Find all the next greater numbers for\u00a0nums1<\/code>‘s elements in the corresponding places of\u00a0nums2<\/code>.<\/p>\n

The Next Greater Number of a number\u00a0x<\/b>\u00a0in\u00a0nums1<\/code>\u00a0is the first greater number to its right in\u00a0nums2<\/code>. If it does not exist, output -1 for this number.<\/p>\n

Example 1:<\/b><\/p>\n

Input: nums1 = [4,1,2], nums2 = [1,3,4,2].\r\nOutput: [-1,3,-1]\r\nExplanation:\r\n    For number 4 in the first array, you cannot find the next greater number for it in the second array, so output -1.\r\n    For number 1 in the first array, the next greater number for it in the second array is 3.\r\n    For number 2 in the first array, there is no next greater number for it in the second array, so output -1.\r\n<\/pre>\n
Example 2:<\/b><\/p>\n
Input: nums1 = [2,4], nums2 = [1,2,3,4].\r\nOutput: [3,-1]\r\nExplanation:\r\n    For number 2 in the first array, the next greater number for it in the second array is 3.\r\n    For number 4 in the first array, there is no next greater number for it in the second array, so output -1.\r\n<\/pre>\n
Note:<\/b><\/p>\n
    \n
  1. All elements in\u00a0nums1<\/code>\u00a0and\u00a0nums2<\/code>\u00a0are unique.<\/li>\n
  2. The length of both\u00a0nums1<\/code>\u00a0and\u00a0nums2<\/code>\u00a0would not exceed 1000.<\/li>\n<\/ol>\n
    Solution 1: Brute Force<\/strong><\/p>\n
    Time complexity: O(n^2)<\/p>\n
    Space complexity: O(1)<\/p>\n
    \/\/ Author: Huahua\r\n\/\/ Running time: 13 ms\r\nclass Solution {\r\npublic:\r\n  vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) {\r\n    vector<int> ans;\r\n    for (int num : findNums) {\r\n      ans.push_back(-1);\r\n      int index = std::find(nums.begin(), nums.end(), num) - nums.begin();\r\n      for (int i = index; i < nums.size(); ++i)\r\n        if (nums[i] > num) {\r\n          ans.back() = nums[i];\r\n          break;\r\n        }\r\n    }\r\n    return ans;\r\n  }\r\n};<\/pre>\n
    Solution 2: HashTable + Brute Force<\/strong><\/p>\n
    Time complexity: O(n^2)<\/p>\n
    Space complexity: O(n)<\/p>\n
    C++<\/p>\n
    \/\/ Author: Huahua\r\n\/\/ Running time: 15 ms\r\nclass Solution {\r\npublic:\r\n    vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) {\r\n      unordered_map<int, int> indices;\r\n      for (int i = 0 ; i < nums.size(); ++i)\r\n        indices[nums[i]] = i;\r\n      vector<int> ans;\r\n      for (int num : findNums) {\r\n        ans.push_back(-1);\r\n        for (int i = indices[num]; i < nums.size(); ++i)\r\n          if (nums[i] > num) {\r\n            ans.back() = nums[i];\r\n            break;\r\n          }\r\n      }\r\n      return ans;\r\n    }\r\n};<\/pre>\n
    Solution 3: Stack + HashTable<\/strong><\/p>\n
    Using a stack to store the nums whose next greater isn’t found yet.<\/p>\n
    \/\/ Author: Huahua\r\n\/\/ Running time: 11 ms\r\nclass Solution {\r\npublic:\r\n  vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) {\r\n    stack<int> s;\r\n    unordered_map<int, int> next;\r\n    for (int num : nums) {\r\n      while (!s.empty() && num > s.top()) {\r\n        next[s.top()] = num;\r\n        s.pop();\r\n      }\r\n      s.push(num);\r\n    }\r\n      \r\n    vector<int> ans;\r\n    for (int num : findNums)\r\n      ans.push_back(next.count(num) ? next[num] : -1);\r\n    return ans;\r\n  }\r\n};<\/pre>\n
     <\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"
    \u9898\u76ee\u5927\u610f\uff1a\u7ed9\u4f60\u4e00\u4e2a\u7ec4\u6570A\u91cc\u9762\u6bcf\u4e2a\u5143\u7d20\u90fd\u4e0d\u76f8\u540c\u3002\u518d\u7ed9\u4f60\u4e00\u4e2a\u6570\u7ec4B\uff0c\u5143\u7d20\u662fA\u7684\u5b50\u96c6\uff0c\u95ee\u5bf9\u4e8eB\u4e2d\u7684\u6bcf\u4e2a\u5143\u7d20\uff0c\u5728A\u6570\u7ec4\u4e2d\u76f8\u540c\u5143\u7d20\u4e4b\u540e\u7b2c\u4e00\u4e2a\u6bd4\u5b83\u7684\u5143\u7d20\u662f\u591a\u5c11\u3002 Problem: You are given two arrays\u00a0(without duplicates)\u00a0nums1\u00a0and\u00a0nums2\u00a0where\u00a0nums1\u2019s elements are subset of\u00a0nums2. Find all the next greater numbers for\u00a0nums1‘s elements in the corresponding places of\u00a0nums2.…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[184],"tags":[20,82,180],"class_list":["post-1970","post","type-post","status-publish","format-standard","hentry","category-array","tag-array","tag-hashtable","tag-stack","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1970","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=1970"}],"version-history":[{"count":7,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1970\/revisions"}],"predecessor-version":[{"id":1977,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1970\/revisions\/1977"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=1970"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=1970"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=1970"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}