【LeetCode力扣】单调栈解决Next Greater Number（下一个更大值）问题

1、题目介绍

示例1：

输入：nums1 = [4,1,2], nums2 = [1,3,4,2].

输出：[-1,3,-1]

解释：nums1 中每个值的下一个更大元素如下所述：

- 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。

- 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。

- 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。

实例2：

输入：nums1 = [2,4], nums2 = [1,2,3,4].

输出：[3,-1]

解释：nums1 中每个值的下一个更大元素如下所述：

- 2 ，用加粗斜体标识，nums2 = [1,2,3,4]。下一个更大元素是 3 。

- 4 ，用加粗斜体标识，nums2 = [1,2,3,4]。不存在下一个更大元素，所以答案是 -1 。

提示：

• 1 <= nums1.length <= nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 10^4
• nums1和nums2中所有整数 互不相同
• nums1 中的所有整数同样出现在 nums2 中

2、解题思路

       该题如果使用暴力破解法，其代码实现过程是很容易想到的，只需要找到nums1此时的元素在nums2中的位置，并向右查询是否存在更大的值，有则返回该值，无则返回-1即可。结合思想不难想到时间复杂度为O(m*n)，m和n分别为两个数组各自的长度。虽然该题直接使用暴力破解法可以直接通过，但是只是出题人没有为难大家，如果该题的数据非常庞大，此时直接使用暴力破解法必然会导致超时。而本文将讲解单调队列的算法模版解决这类问题，它能够很好的将时间复杂度控制在O(m+n)。

下面将使用两种方法来解题，一种是暴力破解法，一种是Next Greater Number问题解法。

2.1、暴力破解法

从头开始遍历nums1，每次遍历从nums2中找到对应元素，然后从该元素的下一个元素开始依次比较，找出大于该值的第一个元素即可。

【代码实现】

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int[] res = new int[m];
        for (int i = 0; i < m; ++i) {
            int j = 0;
            while (j < n && nums2[j] != nums1[i]) {  //在nums2中找到该值
                ++j;
            }
            int k = j + 1;
            while (k < n && nums2[k] < nums2[j]) {   //从该值的下一个元素开始向右查找
                ++k;
            }
            res[i] = k < n ? nums2[k] : -1;    //超出nums2数组长度则表示不存在比该值大的数，返回-1
        }
        return res;
    }
}

时间复杂度：O(m*n)，m和n分别为两数组的长度。

空间复杂度：O(1)。

2.2、经典Next Greater Number问题解法

首先需要补充一些知识点，下面用一个比较抽象的例子讲解：

把数组的元素想象成并列站立的人，元素大小想象成人的身高。视线从左往右，这些人面对你站成一列。如何求第一个元素【2】的下一个更大值呢？，其实很简单，只要没被该元素【2】挡住的第一个元素，就是【2】的下一个更大值，如下图所示，第一个【2】没有挡住的第一个元素就是【4】，此时【4】就是【2】的下一个更大值。

当理解了这个前提后，我们从后往前遍历该数组：

【3】，【3】背后看不到任何元素，即没有比它更大的右元素，因此next greater为-1；

【4】，【4】背后依然看不到任何元素（3被挡住了），此时next greater为-1；

【2】，【2】背后看到的第一个元素是4，因此next greater为4；（绿色2）

【1】，【1】背后看到的第一个元素是2，因此next greater为2；

【2】，【2】背后看到的第一个元素是4，因此next greater为4；（蓝色2）

在代码中为了记录某个值背后没被挡住的第一个元素，这里使用栈stack来记录，入栈出栈规则：当前值比栈中元素大时（证明被挡住了），将该值出栈，直至栈空或当前值小于栈顶元素，此时栈顶元素即为next greater；随后将当前值入栈。

因此我们需要做的就是从后往前遍历nums2数组，并计算出nums2对于的next greater，同时使用Map将【nums2的该值】以及【该值的next greater】记录下来，最后遍历nums1数组，从Map中取出对应值的next greater存入返回数组ret中即可。下面是代码实现部分。

【代码实现】

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Stack<Integer> stack = new Stack<>();
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = nums2.length - 1; i >= 0; i--) {   //从后往前
            int num = nums2[i];
            while(!stack.isEmpty() && stack.peek() <= num) {   //栈内元素小于等于当前值时，出栈
                stack.pop();       //让栈始终保持只有【大于】当前值的元素
            }
            map.put(num,stack.isEmpty() ? -1 : stack.peek());   //map记录该值的下一个最大值，没有则-1
            stack.push(num);
        }
        int[] ret = new int[nums1.length];
        for(int i = 0; i < nums1.length; i++) {    //将map中的对应值取出存入返回数组
            ret[i] = map.get(nums1[i]);
        }
        return ret;
    }
}

时间复杂度：O(m+n)，m和n分别为两数组的长度。

空间复杂度：O(n)，用于存储哈希表。