LeetCode 739. 每日温度 | Python

739. 每日温度

题目来源：力扣（LeetCode）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] 范围内的整数。

解题思路

思路：单调栈

先理清题意，题目中的意思是每个元素往右边找到第一个比它大的元素，计算两者间的距离。

那么使用暴力解的话，代码大致如下：

def dailyTemperatures(self, T: List[int]) -> List[int]:
    length = len(T)

    ans = [0] * length

    for i in range(length):
        for j in range(i+1, length):
            if T[i] < T[j]:
                ans[i] = j - i
                break

    return ans

这里，执行会超时。

我们需要去优化，使用栈，用空间换时间。

从前面的暴力解也可以看出来，解决问题主要需要关注的就是右边的元素的大小。

先看看暴力解的主要问题，在遍历数组的时候，寻找下一个元素比当前元素大这块，很大程度都在做重复的查询。

现在希望能够解决的就是，使用栈存储右边的元素，供后续比较，将无需重复比较的元素剔除。

现在我们考虑从右边进行遍历，考虑哪些元素需要剔除？

当我们从右边往左开始遍历时，要保留较大的元素入栈，具体的做法：

当栈为空的情况下，将当前元素入栈；
遍历的时候，如果当前元素比栈顶元素大时，这个时候考虑将栈内的元素出栈，直到栈顶元素大于当前元素；
这个时候，栈顶的元素其实就是当前元素右边第一个比其大的元素，先计算距离，然后将当前的元素入栈，继续遍历
重复上面的步骤，直至遍历结束。

具体的代码实现如下。

代码实现

class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        length = len(T)

        ans = [0] * length

        # 这里借助列表实现
        # 列表末尾元素即是栈顶元素
        stack = []

        # 从右边往左边开始遍历
        for i in range(length - 1, -1, -1):
            # 如果当前元素大于等于栈顶元素时，进行出栈
            # 直至当前元素小于栈顶元素
            while stack and T[i] >= T[stack[-1]]:
                stack.pop()
            
            # 这个时候栈顶元素其实就是当前元素右边第一个比其大的元素，先计算距离，然后入栈
            if stack and T[i] < T[stack[-1]]:
                ans[i] = stack[-1] - i

            # 栈为空的情况下，将当前元素入栈
            stack.append(i)

        return ans

实现结果

总结

先理清题意，题目要求的是每个元素往右找第一个比它大的元素，计算两者间的距离。
先使用暴力解尝试解决问题（Python 编写超时），但是可以发现有部分查询是重复的。尝试使用空间换时间的思路优化。
借助栈，从右往左开始遍历。维护栈内的元素，避免重复查询。具体的做法（遍历从右往左）：
- 当栈为空时，元素入栈；
- 遍历时，当前元素大于等于栈顶元素时，这个时候要进行出栈，直至当前元素小于栈顶元素；
- 这个时候栈顶元素其实就是当前元素右边第一个比它大的元素，计算两者间的距离，然后将当前元素入栈。供下一个 i-1 索引元素作比较。（在这里，前面出栈的元素为何可以剔除，是因为比当前 T[i] 还小的元素，不可能是 T[i-1] 右边第一个比它大的元素）
- 继续遍历直至结束。

文章原创，如果觉得写得还可以，欢迎关注。微信公众号《书所集录》同步更新，同样欢迎关注。

最后编辑于：2020.06.11 18:26:18