题目描述

给你两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。

请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。

nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。

  1. 输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
  2. 输出: [-1,3,-1]
  3. 解释:
  4.     对于 num1 中的数字 4 ，你无法在第二个数组中找到下一个更大的数字，因此输出 -1 。
  5.     对于 num1 中的数字 1 ，第二个数组中数字1右边的下一个较大数字是 3 。
  6.     对于 num1 中的数字 2 ，第二个数组中没有下一个更大的数字，因此输出 -1 。
  1. 输入: nums1 = [2,4], nums2 = [1,2,3,4].
  2. 输出: [3,-1]
  3. 解释:
  4.     对于 num1 中的数字 2 ，第二个数组中的下一个较大数字是 3 。
  5.     对于 num1 中的数字 4 ，第二个数组中没有下一个更大的数字，因此输出 -1 。

解题思路

使用单调栈。

就是新开辟一个辅助栈，每次新元素入栈后，栈里的元素都保持单调递增或单调递减。

靠的是删除元素来保持栈的单调性。

  1. public int[] nextGreaterElement(int[] nums1, int[] nums2) {
  2.     // 先求出 nums2 中每个元素的下一个最大值
  3.     // 之后 nums1 再去 map 中来找答案即可，因为 nums1 是 nums2 的子集， nums1 要的答案 nums2 肯定都有
  4.     // map 中键存储 nums2 数组，值存储 nums2 数组的每个元素对应在 nums2 数组中的下一个更大元素的值
  5.     Map<Integer, Integer> map = new HashMap<>(); 
  7.     // 单调栈: 存放 nums2 的当前元素及其后面比它大的元素的栈，后面元素是依次递增的
  8.     Stack<Integer> stack = new Stack<>();  
  10.     // 因为题目要求是 "下一个" 更大的元素，所以要从 nums2 的最后面开始遍历
  11.     for (int i = nums2.length - 1; i >= 0; i--) {  
  13.         // nums2 当前元素比 stack 的栈顶元素大
  14.         while (!stack.isEmpty() && stack.peek() <= nums2[i]) { 
  15.             // 将栈顶元素 pop 掉，然后将 nums2 当前元素入栈，但在入栈前要先得到题目要求的正确答案后再入栈
  16.             stack.pop();  
  17.         }
  19.         // 当前元素之后的第一个比它大的值，因为当前元素是在下一行才入栈,所以不会出现等于的情况，一定是比它大的
  20.         map.put(nums2[i], stack.isEmpty() ? -1 : stack.peek());  
  22.         // 当前元素入栈，等待下一轮它的前一个元素与它比较
  23.         stack.push(nums2[i]); 
  24.     }
  26.     /**************************************************************************/
  27.     // 题目要求返回 int[], 用来存储答案的数组
  28.     int[] result = new int[nums1.length]; 
  30.     // nums1 就可以从 map 中存储着 nums2 的键来找到正确的值答案
  31.     for (int i = 0; i < nums1.length; i++) { 
  32.         result[i] = map.get(nums1[i]);
  33.     }
  35.     return result;
  36. }