LeetCode 503 Next Greater Element II
概述
https://leetcode.com/problems/next-greater-element-ii/
直接法
暴力方法依然是遍历，直到遇到自己。
实现过程中要注意，当 i 为 0 而 j 越界时我们会将其重置为 0，此后务必要手动验证一下循环继续条件，否则将导致死循环。
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
vector<int> ans(nums.size(), -1);
for (int i = 0; i < nums.size(); i ++) {
for (int j = i + 1; j != i; j ++) {
if (j == nums.size()) j = 0;
if (j == i) break; // if you mannually change the value of j, you must mannually verify the condition
if (nums[j] > nums[i]) {
ans[i] = nums[j];
break;
}
}
}
return ans;
}
};
数组翻倍 + 单调栈
https://labuladong.gitee.io/algo/2/20/51/
用取余来模拟数组翻倍，同时利用后续值覆盖掉前一半不正确的值。
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
int n = nums.size();
vector<int> ans(n, -1);
stack<int> s;
for (int i = 2 * n - 1; i >= 0; i --) {
while (!s.empty() && s.top() <= nums[i % n]) {
s.pop();
}
if (!s.empty()) {
ans[i % n] = s.top();
}
s.push(nums[i % n]);
}
return ans;
}
};