计算机科学基础leetcode刷题单调栈
Source
Edit
History

503. 下一个更大元素 II

Problem: 503. 下一个更大元素 II

思路

  • 题目与每日温度几乎一致

  • 注意结果集初始化为-1

  • 用取模来代替拼接数组

  • 循环时直接用 nums.size() * 2

  • 注意从1开始遍历

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

[]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        vector<int> res(nums.size(),-1);
        stack<int> st;
        st.push(0);
        for (int i = 1; i < nums.size() * 2; i++) {
            if (nums[i % nums.size()] <= nums[st.top()]) {
                st.push(i % nums.size());
            } else {
                while (!st.empty() && nums[i % nums.size()] > nums[st.top()]) {
                    res[st.top()] = nums[i % nums.size()];
                    st.pop();
                }
                s.push(i % nums.size());
            }
        }
        return res;
    }
};