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

## 题目描述

[503. 下一个更大元素 II](https://leetcode-cn.com/problems/next-greater-element-ii/) [739. 每日温度](https://leetcode-cn.com/problems/daily-temperatures/)

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

示例 1:

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

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

## 解题思路

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

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

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

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

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

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

```python
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
```

## 参考资料

* [动画讲解：单调栈](https://leetcode-cn.com/problems/next-greater-element-ii/solution/dong-hua-jiang-jie-dan-diao-zhan-by-fuxu-4z2g/)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kerasnoone.gitbook.io/garnet/suan-fa/zhan/503-xia-yi-ge-geng-da-yuan-su-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.