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

题目描述

思路

由于此题是环形数组，我们在利用单调栈模板的基础上还需要将给定数组扩大一倍，但实际上我们只需要利用取余的操作模拟扩大数组即可（具体操作看代码。在解决有关环形数组的问题时大多数都会涉及到取余操作）

复杂度

时间复杂度:

$O(n)$；其中$n$为数组nums的长度

空间复杂度:

$O(n)$

Code

class Solution {
    /**
     * Next Greater Element II
     *
     * @param nums Given array
     * @return int[]
     */
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        Stack<Integer> stack = new Stack<>();
        for (int i = 2 * n - 1; i >= 0; --i) {
            while (!stack.isEmpty() && stack.peek() <= nums[i % n]) {
                stack.pop();
            }
            res[i % n] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(nums[i % n]);
        }
        return res;
    }
}