503. 下一个更大元素 II

给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。

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

示例 1:

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

示例 2:

1
2
输入: nums = [1,2,3,4,3]
输出: [2,3,4,-1,4]

解题思路

核心思路是单调栈 + 数组翻倍模拟循环，通过将数组复制一份拼接在末尾（模拟循环），利用单调栈高效找到每个元素的下一个更大元素：

  1. 模拟循环数组：
    • 将原数组 nums 复制一份并拼接在末尾（如 [1,2,1] 变为 [1,2,1,1,2,1]），这样无需额外处理循环边界，可直接线性遍历。
  2. 单调栈求解：
    • 使用单调栈存储元素索引，栈内元素对应的数值保持递减顺序；
    • 遍历拼接后的数组，对于每个元素nums[i % n] （n为原数组长度）：
      • 当栈不为空且栈顶元素对应的数值小于当前元素时，当前元素是栈顶元素的下一个更大元素，记录结果并弹出栈顶；
      • 将当前索引 i 压入栈（仅处理原数组范围内的索引，避免重复计算）。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n, -1);  // 初始化结果为-1
        stack<int> st;  // 单调栈，存储索引（对应原数组的索引）
        
        // 遍历两倍长度的数组，模拟循环
        for (int i = 0; i < 2 * n; ++i) {
            int current = nums[i % n];  // 当前元素值（循环取数）
            
            // 栈非空且栈顶元素对应的数值 < 当前元素，说明找到下一个更大元素
            while (!st.empty() && nums[st.top()] < current) {
                int idx = st.top();  // 栈顶元素的索引（原数组范围内）
                st.pop();
                ans[idx] = current;  // 记录下一个更大元素
            }
            
            // 仅将原数组范围内的索引入栈（避免重复处理）
            if (i < n) {
                st.push(i);
            }
        }
        
        return ans;
    }
};