503. The next larger element II

This is the 27th day of my participation in the August Genwen Challenge.More challenges in August

Given a loop array (the next element to the last element is the first element of the array), print the next larger element of each element. The next larger element of the number X is traversed in array order, and the first larger element after that number means that you should search for its next larger element in a loop. If it does not, it prints -1.

Example 1:

Input: [1,2,1] Output: [2,-1,2] Explanation: The next larger number of the first 1 is 2; The number two can’t find the next larger number; The next largest number of the second 1 is searched in a loop, which also results in a 2. Note: The length of the input array cannot exceed 10000.

Their thinking

Maintain a monotonically increasing stack, because it traverses from left to right, so the position of the element closer to the top of the stack is closer to that of the current element, and monotonically increasing from the top of the stack to the bottom of the stack, so when you just keep going out of the stack until you hit something larger than the current element, you just push the current element onto the stack.

code

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

        int n=nums.length;
        Stack<Integer> stack=new Stack<>();

        int[] ints = new int[n];
        Arrays.fill(ints,-1);
        boolean[] booleans = new boolean[n];
        for (int i = n-1; i >=0; i--) {
            if(booleans[i]) continue;
            while(! stack.isEmpty()&&nums[i]>=stack.peek())// Find one larger than the current element
                stack.pop();
            if(! stack.isEmpty())// If there is one larger than the current element, add the result and mark it as found
            {
                ints[i]=stack.peek(); booleans[i]=true;
            } 
            stack.push(nums[i]);
        }
        for (int i = n-1; i >=0; i--) {// It is a loop array, so it needs to be evaluated again
            if(booleans[i]) continue;
            while(! stack.isEmpty()&&nums[i]>=stack.peek()) stack.pop();if(! stack.isEmpty()) { ints[i]=stack.peek(); booleans[i]=true;
            }
            stack.push(nums[i]);
        }
        returnints; }}Copy the code

Time complexity: O(n), where n is the length of the sequence. We need to traverse each element of the array no more than two times, and each element is pushed and unloaded no more than four times in total.

Spatial complexity: O(n), where n is the length of the sequence. The complexity of the space depends largely on the size of the stack, which is at most 2n-1.

503. The next larger element II