Problem

The next greater element of some element x in an array is the first greater element that is to the right of x in the same array.
You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2.
For each 0 <= i < nums1.length, find the index j such that nums1[i] == nums2[j] and determine the next greater element of nums2[j] in nums2. If there is no next greater element, then the answer for this query is -1.
Return an array _ans of length nums1.length such that ans[i] is the next greater element as described above._

Example 1:

  1. Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
  2. Output: [-1,3,-1]
  3. Explanation: The next greater element for each value of nums1 is as follows:
  4. - 4 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.
  5. - 1 is underlined in nums2 = [1,3,4,2]. The next greater element is 3.
  6. - 2 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.

Example 2:

  1. Input: nums1 = [2,4], nums2 = [1,2,3,4]
  2. Output: [3,-1]
  3. Explanation: The next greater element for each value of nums1 is as follows:
  4. - 2 is underlined in nums2 = [1,2,3,4]. The next greater element is 3.
  5. - 4 is underlined in nums2 = [1,2,3,4]. There is no next greater element, so the answer is -1.

Solution

核心思路

下一个最大值之类的问题的解法都是单调栈

  1. 先遍历 nums2
    1. 使用单调栈来算每个元素的 NGE
    2. 使用 HashMap 来存每个元素对应
  2. 再遍历 nums1，从map中取值就完事儿了

单调递减栈的具体推演

这个问题的重点就是 nums2 = [1,3,4,2] 这个数组每个数字分别的下一个最大的元素。

我们建一个Stack stack，然后遍历 nums，来

  1. index = 0
    1. 1 入栈，此时的栈 = 【1】
  2. index = 1
    1. 由于新元素3大于栈顶的元素1，所以1的NGE就找到了，存入map
    2. 此时 1 这个元素的历史使命就完成了，可以把它pop出去了，然后再把3入栈，这样也符合单调递减栈
    3. 此时的栈 = 【3】
  3. index = 2
    1. 新元素是 4，大于栈顶元素的3，同理，把3出栈，存进map，再把4入栈
    2. 此时的栈 = 【4】
  4. index = 2
    1. 新元素是 2，小于栈顶元素的4，直接入栈
    2. 此时的栈 = 【4, 2】

最后我们发现map里的key，只有 1 和 3，因为对于4，2来说，都没有下一个最大的元素