The topic of dry

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.Copy the code

Source: LeetCode link: leetcode-cn.com/problems/ne… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Method: the stack

In fact, this problem is similar to 739 daily temperature, the only difference is that this problem does not calculate the step size and the array is cyclic. So we just need to build on that problem and change the step size calculation to our current loop through the element.

We will loop through the array twice by setting length to length*2 and I to I %(length*2)

Code implementation:

/ * * *@param {number[]} nums
 * @return {number[]}* /
var nextGreaterElements = function (nums) {
    let stack = [];
    let length=nums.length;
    let newArray=new Array(length).fill(-1);
    for (let i = 0; i < nums.length * 2; i++) {
        while(stack.length ! =0 && nums[stack[stack.length - 1]] < nums[i%length]) {
            let pop=stack.pop();
            newArray[pop]=nums[i%length];
        }
        stack.push(i%length)
    }
    return newArray
};
Copy the code