Tag stack - stack monotonically preparatory knowledge - lt. 739. The daily temperature

lt.739. 每日温度

[案例需求]

[思路分析一, 双重for循环遍历]

/** * 最简单莫过于双重循环,笔试时至少不会丢分 * 时间复杂度：O(n^2) * 空间复杂度：O(n) */
 //The outer loop iterates over the given array one at a time, The inner loop is constantly looking for a number larger than the element traversed by the outer loop at this time, 
 //并用resContinue to record the largestindex差值
public int[] dailyTemperatures(int[] T) {
    
    int[] res = new int[T.length];
    for (int i = 0; i < T.length - 1; i++) {
    
        for (int j =  i + 1; j < T.length; j++) {
    
            if (T[j] > T[i]) {
    
                res[i] = j - i;
                break;
            }
        }
    }
    return res;
}

[思路分析二, Simple principle of monotonic stack]

通常是一维数组, To find the position of the first element to the right or left of an element that is larger or smaller than itself, At this point we can think of using a monotonic stack.

• This problem is to find the first element to the right of an element that is larger than itself, So you can use a monotonic stack.

那么单调栈的原理是什么呢？为什么时间复杂度是O(n)就可以找到每一个元素的右边第一个比它大的元素位置呢？

单调栈的本质是空间换时间, 因为在遍历的过程中需要用一个栈来记录右边第一个比当前元素高的元素, 优点是只需要遍历一次.

[单调栈的使用]

• Using a monotonic stack is first explicit:

1. 单调栈里存放的元素是什么?

单调栈里只需要存放元素的下标i就可以了,如果需要使用对应的元素,直接T[i]就可以获取.

2. Whether the elements in a monotonic stack are incremented or decremented?

从栈顶到栈底的顺序

• 本题, We're going to use increasing order（Again, it refers to the order from the top of the stack to the bottom of the stack）,因为只有递增的时候,Adds an element to the stacki,才知道栈顶元素在数组中右面第一个比栈顶元素大的元素是i (curreentIndex, 即当前forThe index of the number to loop through is i).

[具体思路 + 代码实现]

• 维护一个存储下标的单调栈, 从栈底到栈顶的下标对应的温度列表中的温度依次递减, If a subscript is on the monotonic stack, 则表示尚未找到下一次温度更高的下标.
• 正向遍历温度列表, 对于温度列表中的每个元素 T[i], 如果栈为空, 则直接将i进栈, 如果栈不为空, 则比较栈顶元素preIndex对应温度T[preIndex]和当前温度T[i], 如果T[i] > T[preIndex], 则将preInndex移除, 并将preIndexThe corresponding days are assigned as i - preIndex, 重复上述操作, 直到栈为空, Or the temperature corresponding to the top element of the stack is less than or equal to the current temperature, 然后将i出栈.

class Solution {
    
    public int[] dailyTemperatures(int[] temperatures) {
    
        //维护递减栈,The last element on the stack is always smaller than the top element.
        //Compare the size of the current element with the top element of the stack
        //若当前元素 < 栈顶元素：入栈
        /若当前元素 > 栈顶元素：弹出栈顶元素,Record the difference between the two subscripts as the required number of days
        //The stack record is used here T 的下标.
        Deque<Integer> stack = new LinkedList<>();

        int len = temperatures.length;
        int[] res = new int[len];
        int index = 0;

         for(int i = 0; i < len; i++){
    
            int temperature = temperatures[i];
            //当前元素 > 栈顶index的元素
                //弹出preIndex, 记录preIndex与当前元素i的index差值, 更新到res[preIndex]
            while(!stack.isEmpty() && temperature > temperatures[stack.peek()]){
    
                int preIndex = stack.pop();
                System.out.println("i为: " + preIndex);
                //System.out.println("preIndex为: " + preIndex);
                res[preIndex] = i - preIndex;
                System.out.println(Arrays.toString(res));
            }
            //当前元素 <= 栈顶index的元素
                //push the current element on the stack
            stack.push(i);
        } 

        return res;
    }
}