503.下一个更大元素II next-greater-element-ii

问题描述

503.下一个更大元素II

解题思路

相比496.下一个更大元素I，在遍历数组上有所区别，如果i >= nums.size()，用j = i - nums.size();来代替i，因此i的取值范围是[0, 2 * nums.size())。

代码

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