lt.739. 每日温度

[案例需求]

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

/**
 * 最简单莫过于双重循环，笔试时至少不会丢分
 * 时间复杂度：O(n^2)
 * 空间复杂度：O(n)
 */
 //外层循环是一次遍历给定数组, 内层循环是不断的寻找比外层循环此时遍历到的元素大的数, 
 //并用res持续的记录下最大的index差值
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

[思路分析二, 单调栈简单原理]

通常是一维数组, 要寻找一个元素的右边或者左边第一个比自己大或者小的元素的位置, 此时我们就可以想到用单调栈。

• 本题就是找到一个元素右边第一个比自己大的元素, 所以可以用单调栈。

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

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

[单调栈的使用]

• 使用单调栈首先明确:

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

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

2. 单调栈里元素是递增还是递减的?

从栈顶到栈底的顺序

• 本题, 我们要使用递增循序（再强调一下是指从栈顶到栈底的顺序），因为只有递增的时候，往栈中加入一个元素i，才知道栈顶元素在数组中右面第一个比栈顶元素大的元素是i (curreentIndex, 即当前for循环遍历到的数的索引为i)。

[具体思路 + 代码实现]

• 维护一个存储下标的单调栈, 从栈底到栈顶的下标对应的温度列表中的温度依次递减, 如果一个下标在单调栈中, 则表示尚未找到下一次温度更高的下标。
• 正向遍历温度列表， 对于温度列表中的每个元素 T[i], 如果栈为空, 则直接将i进栈, 如果栈不为空, 则比较栈顶元素preIndex对应温度T[preIndex]和当前温度T[i], 如果T[i] > T[preIndex], 则将preInndex移除, 并将preIndex对应的天数赋为i - preIndex, 重复上述操作, 直到栈为空, 或者栈顶元素对应的温度小于等于当前温度, 然后将i出栈.

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        //维护递减栈，后入栈的元素总比栈顶元素小。
        //比对当前元素与栈顶元素的大小
        //若当前元素 < 栈顶元素：入栈
        /若当前元素 > 栈顶元素：弹出栈顶元素，记录两者下标差值即为所求天数
        //这里用栈记录的是 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的元素
                //入栈当前元素
            stack.push(i);
        } 

        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32