503. Next Greater Element II

發表於 | 分類於

problem

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        vector<int> ret(n,-1);
        stack<int>sta;
        for(int i=0;i<n*2;++i){
            while(!sta.empty() && nums[sta.top()%n] <  nums[i%n]){
                int t =sta.top();
                sta.pop();
                ret[t%n] = nums[i%n];
            }
            sta.push(i% n);
        }
        for(int r:ret) cout<<r<<" ";
        return ret;
    }
};

analysis

  • time complexity O(n)
  • space complexity O(n)