[503][中等][栈] 下一个更大元素 II

题目描述

503. 下一个更大元素 II 739. 每日温度

给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。

示例 1:

输入: [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数； 
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。

注意: 输入数组的长度不会超过 10000。

解题思路

如果元素在递增的子序列中, 那么它的下一个更大元素就是它之后的一个元素. 但如果元素在递减子序列中, 那么要一直遍历到下一个更大的元素, 而且这个元素之后且位于这个递减子序列中的其他元素, 对应的下一个更大元素也是这一个.

因此我们的思路是将这种递减的序列保存在栈中, 直到找到下一个较大的元素. 栈中保存的元素从栈底到栈顶将是递减的. 将这个较大的元素依次与栈顶元素比较, 如果栈顶元素更小, 说明栈顶元素找到它对应的下一个更大元素, 从栈中弹出, 并记录当前这个元素值为它的下一个更大元素. 重复这个操作, 直到栈为空, 说明之前的所有元素都找到了下一个更大元素, 或栈顶的元素不小于当前元素, 说明这个元素的下一个更大元素还要继续寻找.

这里的操作其实就是在构建单调栈, 而且是单调递减栈. 构建的过程可以参考[面试题 03.05][中等] 栈排序, 但不同的是将小于当前元素的栈顶元素拿出后, 就不再放回, 而是这个元素已经找到了结果, 去记录当前元素为它的下一个更大元素即可.

由于将元素弹出时, 我们要找到这个元素的位置, 从而修改记录每个元素下一个更大元素的对应位置, 因此我们在入栈时, 将元素对应的索引压入, 方便定位. 这样比较时, 就要多一步从索引到元素值的查找过程了.

另外, 由于是循环数组, 在第一遍遍历完整个数组后, 还需继续遍历, 具体是除了最后一个元素, 要遍历两边数组的每一个元素.

可以想象的是, 最后栈中剩余的元素将是数组中最大值对应的索引. 因为它(们)找不到更大的值.

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        k = len(nums)
        result = [-1] * k
        stack = []
        for i in range(2 * k - 1):
            i = i % k
            while stack and nums[stack[-1]] < nums[i]:
                index = stack.pop()
                result[index] = nums[i]
            stack.append(i)
        return result

参考资料

• 动画讲解：单调栈