Monotonic stack -503 Next bigger Element II

1. Their thinking

First , Determine the solution idea of this problem , The title requires to record the value greater than this number on the right of each number , The essence is to find the nearest value larger than the current number to the right , And the title explains that the array is a circular array .

Decide to use monotone stack to solve this problem ：

Monotonous stack usage scenarios ： It's usually a one-dimensional array , To find the position of the first element larger or smaller than yourself on the right or left of any element , At this point, we have to think of using monotone stack .

2. difficulty

This problem is a little more difficult , Is to turn the array into a circular array , You only need to take the remainder .

3. Code

 public int[] nextGreaterElements(int[] nums) {
    

        int len=nums.length;
        int[] result=new int[nums.length];
        for (int i=0;i<result.length;i++){
    
            result[i]=-1;
        }
        Stack<Integer> stack = new Stack<>();
        stack.push(0);

        for (int i=1;i<len*2;i++){
    
            while (!stack.isEmpty() && nums[(i%len)]>nums[stack.peek()]){
    
                if (result[stack.peek()]==-1){
    
                    result[stack.peek()]=nums[i%len];

                }
                stack.pop();
            }
            stack.push(i%len);
        }

        return result;
    }

4. performance

• Time complexity ：O(n)
• Spatial complexity ：O(n)