1 单调栈 leetcode496 下一个更大元素

题目描述

给定两个没有重复元素的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。nums1 中数字 x的下一个更大元素是指 x在 nums2 中对应位置的右边的第一个比 x大的元素。如果不存在，对应位置输出-1。

示例 1:

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

示例2：

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

注意：

1. nums1和nums2中所有元素是唯一的。
2. nums1和nums2 的数组大小都不超过1000。

官方难度

Easy

解决思路

最简单粗暴的解决思路，两层循环：
输入: nums1 = [2,4], nums2 = [1,2,3,4].

1. 遍历nums1，得到当前元素i 即 2.
2. 遍历nums2，得到元素 i (2) 在当前nums2中的下标start.
3. 从start开始找到nums2大于i (2)的元素 3。

优化

这个题目考的是单调栈， 栈中存的是递减的数字，即当前输入元素是否大于栈顶元素，如果大于则出栈，否则将当前元素入栈。因为只有在当前元素大于栈顶元素的时候才出栈，因此，当出栈的时候，当前元素即为栈顶元素的下一个最更大值，可以构造出栈元素与下一个最大元素的映射，。以输入[1,9,3,2,5]为例子.

1. 初始化记忆字典memo, 并且1入栈
2. 下一个元素9判断是否大于栈顶元素1，大于则出栈，memo[1] = 9 并且将9入栈；
3. 下一个3判断是否大于栈顶元素9， 小于则入栈。
4. 下一个2判断是否大于栈顶元素3， 小于则入栈。
5. 下一个5判断是否大于栈顶元素2， 大于则出栈, memo[2] = 5 。
6. 继续判断下一个5判断是否大于栈顶元素3， 大于则出栈, memo[3] = 5 。
7. 继续判断下一个5判断是否大于栈顶元素9， 小于则入栈。

最终栈的结果为 [9, 5]，遍历nums1，如果当前元素不在memo中则添加-1，否则添加memo中存储的结果。

根据上面的分析，我们可以很容易的得到直接方案的流程如下：

1. 遍历nums2, 通过单调递减栈构造记忆函数memo
2. 遍历nums1，如果当前元素不在memo中则添加-1，否则添加memo中存储的结果

基于这个流程，我们可以实现类似下面的代码：

class Solution(object):
    def nextGreaterElement(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        res = []
        stack = []
        memo = {}
        for i in nums2:
            while stack and i > stack[-1]:
                memo[stack[-1]] = i
                stack.pop()
            stack.append(i)
        for j in nums1:
            if j in memo:
                res.append(memo[j])
            else:
                res.append(-1)
        return res

总结

这题为Easy难度，大部分人都能想到暴力破解，但是如果能在面试过程中，不断优化，加入单调栈的思想，面试过程中是可以加分的。