503. 下一个更大元素 II

503. 下一个更大元素 II - 力扣（LeetCode）

描述

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

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

示例 1:

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

示例 2:

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

题解：

注意读题

class Solution { public: vector<int> nextGreaterElements(vector<int>& nums) { int n = nums.size(); vector<int> res(n, -1); stack<int> st; // 存储索引 // 遍历 2 * n 次，模拟循环数组 for (int i = 0; i < 2 * n; ++i) { int idx = i % n; // 真实索引 // 如果当前元素比栈顶元素大，说明找到了“下一个更大” while (!st.empty() && nums[idx] > nums[st.top()]) { res[st.top()] = nums[idx]; st.pop(); } // 只在第一轮（i < n）时入栈，避免重复入栈 if (i < n) { st.push(idx); } } return res; } };