0503. 下一个更大元素 II

• 标签：栈、数组、单调栈
• 难度：中等

题目链接

• 0503. 下一个更大元素 II - 力扣

题目大意

给定一个循环数组 nums（最后一个元素的下一个元素是数组的第一个元素）。

要求：输出每个元素的下一个更大元素。如果不存在，则输出 -1。

• 数字 x 的下一个更大的元素：按数组遍历顺序，这个数字之后的第一个比它更大的数。这意味着你应该循环地搜索它的下一个更大的数。

解题思路

第一种思路是根据题意直接暴力求解。遍历 nums 中的每一个元素。对于 nums 的每一个元素 nums[i]，查找 nums[i] 右边第一个比 nums1[i] 大的元素。这种解法的时间复杂度是 $O(n^2)$。

第二种思路是使用单调递增栈。遍历数组 nums，构造单调递增栈，求出 nums 中每个元素右侧下一个更大的元素。然后将其存储到答案数组中。这种解法的时间复杂度是 $O(n)$。

而循环数组的求解方法可以将 nums 复制一份到末尾，生成长度为 len(nums) * 2 的数组，或者通过取模运算将下标映射到 0 ~ len(nums) * 2 - 1 之间。

具体做法如下：

• 使用数组 res 存放答案，初始值都赋值为 -1。使用变量 stack 表示单调递增栈。
• 遍历数组 nums，对于当前元素：
  • 如果当前元素值小于栈顶元素，则说明当前元素「下一个更大元素」与栈顶元素的「下一个更大元素」相同。应该直接让当前元素的下标入栈。
  • 如果当前元素值大于栈顶元素，则说明当前元素是之前元素的「下一个更大元素」，则不断将栈顶元素出栈。直到当前元素值小于栈顶元素值。
    • 出栈时，出栈元素的「下一个更大元素」是当前元素。则将当前元素值存入到答案数组 res 中出栈元素所对应的位置中。
• 最终输出答案数组 res。

代码

size = len(nums)
        res = [-1 for _ in range(size)]
        stack = []
        for i in range(size * 2):
            while stack and nums[i % size] > nums[stack[-1]]:
                index = stack.pop()
                res[index] = nums[i % size]
            stack.append(i % size)

        return res