单调栈模拟题
ref{:target=”_blank”}
C++ 代码
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
int n = nums.size();
// 环形数组处理方法,将原数组copy一份,放在之前数组的尾部
nums.insert(nums.end(), nums.begin(), nums.end());
stack<int> stk;
vector<int> res(n);
// 单调栈求右边第一个大的数
for(int i=nums.size()-1; i>=0; i--) {
int num = nums[i];
// 求大的数,所以 小于等于的数都需要pop出来
while(stk.size() && num >= stk.top())stk.pop();
if(i<n){
if(stk.empty())res[i] = -1;
else res[i] = stk.top();
}
stk.push(num);
}
return res;
}
};