循环解题:
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
int n = nums.size();
vector<int> res;
for (int i = 0; i <n; i++){
int k = i;
bool flag = false;
for (int j = 1;j <=n-1;j++){
if((k+j)%n != k && nums[(k+j)%n]>nums[i]) {
res.push_back(nums[(k+j)%n]);
flag = true;
break;
}
}
if (!flag) res.push_back(-1);
}
return res;
}
};
下面开始理解,
方法一:单调栈+循环数组
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
int n = nums.size();
vector<int> ret(n, -1);
stack<int> stk;
for (int i = 0; i < n * 2 - 1; i++) {
while (!stk.empty() && nums[stk.top()] < nums[i % n]) {
ret[stk.top()] = nums[i % n];
stk.pop();
}
stk.push(i % n);
}
return ret;
}
};
python
class Solution:
def nextGreaterElements(self, nums: List[int]) -> List[int]:
n = len(nums)
ret = [-1] * n
stk = list()
for i in range(n*2 -1):
while stk and nums[stk[-1]] < nums[i%n]:
ret[stk.pop()] = nums[i%n]
stk.append(i%n);
return ret