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

This problem requires us to find the next greater number of each number in nums. We can use decreasing monotonic stack to solve it. It mentions that nums is circularly, so we can double nums, which simplifies the circularity. Because we are looking for the next greater number on the right, we have to build a decreasing monotonic stack from the end. Before pushing numbers into the stack, the last number on the stack is the next greater number. If the stack is empty, it means there are no greater numbers, so the value will be -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;
    }
}

Reference

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