37 lines
915 B
C++
37 lines
915 B
C++
#include "s0503_next_greater_element_ii.hpp"
|
|
|
|
// 循环数组首先考虑到的方法就是将两个数组拼接到一起处理。
|
|
// 我们将两个数组拼接到一起，然后用单调栈即可，但这样做有些浪费内存。
|
|
// 另一种处理方式是这样遍历：
|
|
// for (int i{0}; i < 2 * len; ++i) {
|
|
// nums[i % len] ...
|
|
// }
|
|
|
|
vector<int> S0503::nextGreaterElements(vector<int>& nums) {
|
|
int len = nums.size();
|
|
if (len == 0) {
|
|
return vector<int> {};
|
|
} else if (len == 1) {
|
|
return vector<int> {-1};
|
|
}
|
|
vector<int> ans(len, -1);
|
|
stack<int> s;
|
|
for (int i{0}; i < 2 * len; ++i) {
|
|
if (s.empty()) {
|
|
s.push(i);
|
|
continue;
|
|
}
|
|
while (nums[i % len] > nums[s.top() % len]) {
|
|
if (ans[s.top() % len] == -1) {
|
|
ans[s.top() % len] = nums[i % len];
|
|
}
|
|
s.pop();
|
|
if (s.empty()) {
|
|
break;
|
|
}
|
|
}
|
|
s.push(i);
|
|
}
|
|
return ans;
|
|
}
|