503 下一个更大元素II
https://leetcode.cn/problems/next-greater-element-ii/description/
遍历一遍数组显然不够,可复制一份数组拼接在原数组末尾,实现循环数组
实际操作中,我们不需要复制,只需要遍历两次数组即可,i % n 对应nums的下标
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
int n = nums.size();
stack<int> stk;
vector<int> ans(n, -1);
for (int i = 0; i < 2 * n - 1; i++) {
while (!stk.empty() && nums[i % n] > nums[stk.top()]) {
ans[stk.top()] = nums[i % n];
stk.pop();
}
stk.push(i % n);
}
return ans;
}
};
复杂度分析
时间复杂度: O(n),其中 n 是序列的长度。我们需要遍历该数组中每个元素最多 2 次,每个元素出栈与入栈的总次数也不超过 4 次。
空间复杂度: O(n),其中 n 是序列的长度。空间复杂度主要取决于栈的大小,栈的大小至多为 2n−1。