米洛的小窝

每日一题20210306 503. 下一个更大元素 II.md

2022/6/4 leetcode

# 503. 下一个更大元素 II

# 想法

首先和大部分人想的一样，第一反应也是想着用暴力法，复杂度是O(n²)

所以我坐在公交车🚌开始想新的解法，但也只能想出稍微优化的解法，比如[2, 1, 1, 3] 如果找到2的下一个最大值，那么后面的1也不需要继续找了，因为他们比2还小，所以他们的下一个最大值也是8。

想到这里我的思路也就戛然而止了~

# 思路

这种情况下，我们可以使用单调栈来解决问题。我们用一个栈去记录数组元素的下标（因为下标记住了，所以等于记住了这个下标元素的值）

  • 当栈为空的时候，我们把下标直接压入栈。
  • 当栈不为空的时候，我们和栈的顶部元素进行对比:
    • 如果当前元素比顶部元素小，那么直接入栈
    • 如果当前元素大于顶部元素，顶部元素出栈，直到顶部元素比当前元素大为止

# 这样做的目的是为了保证栈是大的在上面，小的在下面，在找到比顶部元素大的数字的时候，就是顶部元素的下一个更大元素

# 注意点

这里存在末尾元素，所以需要遍历数组2次，我们遍历的索引从0-2n即可，可以通过取余获取到当前元素的真实索引。

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        n = len(nums)
        result = [-1] * n
        stack = []
        # 最底下最大
        for i in range(2 * n):
            # 注意i % n是当前数字的真实索引, 因为这里采用了遍历2倍数组长度的做法
            # 当栈不为空，且当前元素比顶部元素大, 则顶部元素要出栈，因为要保证栈单调递减
            while len(stack) > 0 and nums[i%n] > nums[stack[-1]]:
                # stack.pop()让顶部元素出栈，并且返回顶部元素的索引，当前元素>顶部元素，所以赋值给result[顶部元素]
                result[stack.pop()] = nums[i%n]
            stack.append(i%n)
        return result
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 参考题解

leetcode动画题解 (opens new window)