O(n) just like concatenation
单调递减栈
循环扫两遍，下标取模即可
倒序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
stack<int> s;
int n = nums.size(), sz = n << 1;
vector<int> res(n);
for (int i = sz - 1; i >= 0; --i) {
int idx = i % n;
while (!s.empty() && nums[s.top()] <= nums[idx]) {
s.pop();
}
res[idx] = s.empty() ? -1 : nums[s.top()];
s.push(idx);
}
return res;
}
};
|
正序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
stack<int> s;
int n = nums.size(), sz = n << 1;
vector<int> res(n, -1);
for (int i = 0; i < sz; ++i) {
int idx = i % n;
while (!s.empty() && nums[s.top()] < nums[idx]) {
res[s.top()] = nums[idx];
s.pop();
}
s.push(idx);
}
return res;
}
};
|