The topic of dry

Generate a new list based on the daily temperature list. The output of the corresponding position is: the minimum number of days to wait for higher temperatures to be observed. If the temperature does not rise after that point, substitute 0 at that point.

For example, given a list of temperatures = [73, 74, 75, 71, 69, 72, 76, 73], your output would be [1, 1, 4, 2, 1, 1, 0, 0].

** Hint: ** The length range of the temperature list is [1, 30000]. Each temperature is an integer in the [30, 100] range of degrees Fahrenheit.

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

Solution: monotone stack

When I just got this problem, I had no brain violence. It took me milliseconds. Finally, I found that I could use stack to do it.

Basically, we store the subscript of the number that was previously greater than the current loop in our stack (because they’re counting steps). Every time we walk through the temperatures, if the current element is smaller than the element at the top of the stack, we stack it, and if the element is larger than the element at the top of the stack, we pop its subsetvalue, the value at the top of the stack (the step), into a new array. The loop continues to iterate through the elements in the stack until the end.

Code implementation:

/ * * *@param {number[]} temperatures
 * @return {number[]}* /
var dailyTemperatures = function (temperatures) {
    /* Monotonic stack */
    let length = temperatures.length;
    let stack =[];
    let tartgetArray = new Array(length).fill(0)
    for (let i = 0; i < length; i++) {
        let temperaturesValue = temperatures[i]
        while(stack.length ! =0 && temperatures[stack[stack.length - 1]] < temperaturesValue) {
            let pop = stack.pop();
            tartgetArray[pop] = i - pop
        }
        stack.push(i)
    }
    console.log(stack)
    return tartgetArray
};
Copy the code