LeetCode Next Greater Element I You are given two arrays (without duplicates) nums1 and nums2 where nums1’s elements are subset of nums2. Find all the next greater numbers for nums1‘s elements in the corresponding places of nums2. The Next Greater Number of a number x in nums1 is the first greater number to its right in nums2. If it does not exist, output -1 for this number. Example 1:

Input: nums1 = [4,1,2], nums2 = [1,3,4,2].
Output: [-1,3,-1]
Explanation:
    For number 4 in the first array, you cannot find the next greater number for it in the second array, so output -1.
    For number 1 in the first array, the next greater number for it in the second array is 3.
    For number 2 in the first array, there is no next greater number for it in the second array, so output -1.

Example 2:

Input: nums1 = [2,4], nums2 = [1,2,3,4].
Output: [3,-1]
Explanation:
    For number 2 in the first array, the next greater number for it in the second array is 3.
    For number 4 in the first array, there is no next greater number for it in the second array, so output -1.

Note:

1. All elements in nums1 and nums2 are unique.
2. The length of both nums1 and nums2 would not exceed 1000.

---

给定两个数组nums1和nums2，其中nums1是nums2的子集，两个数组中的都没有重复元素。现在要问nums1中的每个数在nums2中其右边第一个更大的数是什么。 比如Example 2中，nums1[0]=2，在nums2中2的右边有3和4，则第一个更大的数是3。 常规思路是对于nums1中的每个数，在nums2中找到位置，并在其右边搜索第一个比它的数。更好一点的解法是，对nums2中的每个数，建立数和下标的hash关系，这样对于nums1中的每个数，就能O(1)找到其在nums2中的位置，直接开始在其右边找更大的数，但是渐进复杂度都是O(n*m)。 代码如下： [cpp] class Solution { public: vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) { unordered_map<int, int> hash; for (int i = 0; i < nums.size(); ++i)hash[nums[i]] = i; vector<int> ans; for (int i = 0; i < findNums.size(); ++i) { int idx = hash[findNums[i]], ret = -1; for (int j = idx + 1; j < nums.size(); ++j) { if (nums[j] > findNums[i]) { ret = nums[j]; break; } } ans.push_back(ret); } return ans; } }; [/cpp] 本代码提交AC，用时9MS。 还有一种比较巧妙的解法，借助栈，用O(m)时间就可以得到nums2中所有数的其右边更大数。具体举例，比如Example 1中nums2 = [1,3,4,2]，先不断压栈，遇到1，压栈；遇到3，发现栈顶原始1比3小，说明1的右边更大数是3，建立hash关系，把1弹栈，栈内没东西了，3进栈。 更极端一点，假设nums2 = [9, 8, 7, 3, 2, 1, 6]，则从9~1都一直压栈，因为后面的数一直比栈顶元素小，当不了栈顶原始的右边更大数。当遇到6时，发现栈顶是1，则6可以当1的右边更大数，把1弹栈；又发现6比当前栈顶2大，又可以当2的右边更大数；如此不断弹栈，直到栈顶为7时，6压栈。此时9~7和6都没有右边更大数。对于没有右边更大树的数，其右边更大数赋值为-1。 代码如下： [cpp] class Solution { public: vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) { unordered_map<int, int> hash; stack<int> stk; for (int i = 0; i < nums.size(); ++i) { while (!stk.empty() && stk.top() < nums[i]) { hash[stk.top()] = nums[i]; stk.pop(); } stk.push(nums[i]); } vector<int> ans; for (int i = 0; i < findNums.size(); ++i) { if (hash.find(findNums[i]) == hash.end())ans.push_back(-1); else ans.push_back(hash[findNums[i]]); } return ans; } }; [/cpp] 本代码提交AC，用时12MS。]]>