503. Next Greater Element II

Problem

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]

Constraints:

• 1 <= nums.length <= 104
• -109 <= nums[i] <= 109

Solution

此題要我們找 nums 中，每個數字的下一個較大的數字。我們可以用 decreasing monotonic stack 來解。題目提到 nums 是循環的，因此我們可以將 nums 延伸一倍，這樣可以簡化循環的處理。因為我們是找右邊下一個較大的數字，所以我們要從後面往前面來建立 decreasing monotonic stack。當要 push 數字進去 stack 之前，stack 最後的數字就是下一個較大的數字。若 stack 是空的時候，那表示沒有較大的數字，因此值會是 -1。

Monotonic Stack

• Time:
• Space:

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        LinkedList<Integer> stack = new LinkedList<>();
        int[] results = new int[n];

        for (int i = n * 2 - 1; i >= 0; i--) {
            while (!stack.isEmpty() && stack.peek() <= nums[i % n]) {
                stack.pop();
            }

            results[i % n] = stack.isEmpty() ? -1 : stack.peek();

            stack.push(nums[i % n]);
        }

        return results;
    }
}

參考

• 503. Next Greater Element II, LeetCode.
• 503. Next Greater Element II, LeetCode Solutions.