LeetCode.739.Daily Temperatures 每日温度

题目描述

739 Daily Temperatures
https://leetcode-cn.com/problems/daily-temperatures/

请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。

---

相似题目

LeetCode.739.Daily Temperatures 每日温度
LeetCode.042.Trapping Rain Water 接雨水
LeetCode.084.Largest Rectangle in Histogram 柱状图中最大的矩形

LeetCode.011.Container With Most Water 盛最多水的容器

---

解题过程

单调栈

这是一个经典的单调栈题目，并且是纯粹的单调栈应用，没有其他复杂逻辑，非常适合作为单调栈的入门题目。

维护一个单调递减栈，栈中存储数组下标，栈空或当前元素 nums[i] 小于等于栈顶元素下标对应的值时入栈，当前元素大于栈顶元素下标对应的值时，循环弹出栈顶并计算当前 i 和每次弹出的栈顶下标 stackPeekIndex 的差值 i - stackPeek，这个值就是下标 stackPeekIndex 位置右侧第一个比他大的元素和他的距离差值。

这里注意一点，单调栈问题中通常有个技巧，在原数组最后补一个虚拟的不可能在数组中存在的最小/大值，最后将其压入栈中，以便触发计算，但是这个题目不需要，因为数组初始化为全 0，对于右侧没有更大值的元素，不需要计算。

时间复杂度 O(n) 因为数组每个元素下标最多有一次进栈出栈。
空间复杂度 O(n)

private static class SolutionV202006 {
    public int[] dailyTemperatures(int[] T) {
        if (null == T || T.length < 1) {
            return T;
        }
        // 结果数组，默认全初始化为 0
        int[] res = new int[T.length];
        // 单调递减栈，栈中存数组下标
        Deque<Integer> monoStack = new LinkedList<>();
        for (int i = 0; i < T.length; i++) {
            // 遇到比栈顶大的元素，循环出栈并计算结果
            while (!monoStack.isEmpty() && T[i] > T[monoStack.peek()]) {
                int stackPeekIndex = monoStack.pop();
                res[stackPeekIndex] = i - stackPeekIndex;
            }
            monoStack.push(i);
        }
        return res;
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_739_DailyTemperatures.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_739_DailyTemperatures.java

---