503. 下一个更大元素 II
- 题目
- 算法设计：单调栈
题目
算法设计：单调栈
前置知识：单调栈原理，请猛击：496. 下一个更大元素 I
和 496. 下一个更大元素 I 这题相同，唯一变化是数组变成了循环数组。
比如输入 [1, 2, 1]，循环数组应该返回 [2, -1, 2]，而不是 [2, -1, -1]，因为拥有了环形属性，最后一个元素 1 绕了一圈后找到了比自己大的元素 2。
对于这种需求，思路是将数组长度翻倍：
- 原数组：2, 3, 1
- 拉直数组：2, 3, 1, 2, 3, 1
这样原数组的末尾 1，就可以找到右边第一个更大的元素 2。
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
stack<int> s;
vector<int> res(nums.size());
for (int i = nums.size() - 1; i >= 0; i--) // 预先存下数组，实现数组翻倍
s.push(nums[i]);
for (int i = nums.size() - 1; i >= 0; i--) {
while (!s.empty() && s.top() <= nums[i])
s.pop();
res[i] = s.empty()? -1: s.top();
s.push(nums[i]);
}
return res;
}
};