[刷题防痴呆] 0503 - 下一个更大的元素 II (Next

题目地址

https://leetcode.com/problems/next-greater-element-ii/

题目描述

503. Next Greater Element II

Given a circular integer array nums (i.e., the next element of nums[nums.length - 1] is nums[0]), return the next greater number for every element in nums.

The next greater number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn't exist, return -1 for this number.

 

Example 1:

Input: nums = [1,2,1]
Output: [2,-1,2]
Explanation: The first 1's next greater number is 2; 
The number 2 can't find next greater number. 
The second 1's next greater number needs to search circularly, which is also 2.
Example 2:

Input: nums = [1,2,3,4,3]
Output: [2,3,4,-1,4]

思路

• 单调栈. 用单调栈维护当前位置还没找到最大值的元素index列表, 从栈底到栈顶的元素单调递减.

关键点

• 与I的区别是环形, 因此可以拼接一遍数组来求解.

代码

• 语言支持：Java

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        Deque<Integer> stack = new ArrayDeque<>();
        int n = nums.length;
        int[] res = new int[n];
        Arrays.fill(res, -1);
        for (int i = 0; i < 2 * n; i++) {
            while (!stack.isEmpty() && nums[stack.peek() % n] < nums[i % n]) {
                int index = stack.pop();
                res[index % n] = nums[i % n];
            }
            stack.push(i);
        }

        return res;
    }
}