跳转至

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。