Loading...
墨滴

大明白

2021/11/03  阅读:25  主题:默认主题

【算法实践】单调栈

单调栈的应用

先来看一道题:

739. Daily Temperatures(每日温度)

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the i(th) day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Example 1: Input: temperatures = [73,74,75,71,69,72,76,73] Output: [1,1,4,2,1,1,0,0]

Example 2: Input: temperatures = [30,40,50,60] Output: [1,1,1,0]

Example 3: Input: temperatures = [30,60,90] Output: [1,1,0]

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/daily-temperatures 著作权归领扣网络所有。

上面这道题有一个暴力解法,即遍历temperatures这个数组,对于每一个温度temperatures[i],都可以向后查找,直到找到其后某一个温度temperatures[j]大于这一天,使用j - i就可以得到差几天。如果没有找到,就写入0。因为需要遍历temperatures拿到temperatures[i],同时对于每一个temperatures[i],还需要遍历一次temperatures,这个算法的复杂度在 O( )。

是否真的有必要对于每一个temperatures[i]都遍历一遍temperatures呢?我们重新来看一下对于一个温度 temperatures[i]的检索过程:从i + 1开始向后遍历,如果temperatures[j]>temperatures[i], 中间的从temperatures[i]temperatures[j]之间的温度其实我们都遍历过,但是这部分信息在计算temperatures[i+1]时,就没有被利用。那么优化的方向就是我们用小本子记住我们曾经遍历过,但是暂时还无法计算出答案的元素。

以何种方式来存储这些暂时无法计算的元素呢?因为如果后面有一天的温度大于前面的一天,就可以计算出答案,如果小于,就无法算出来。也就是说如果后面的元素小于前面的元素,就需要记录下来,所以我们采用一个“有序递减”的结构来存储是最合适的。这就引入了“单调栈”。在这道题里,因为比栈顶小的元素会入栈,所以是“单调递减栈”(※注意,本题入栈的是数组的下标i,但是判断条件是temperatures[i])。

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)      
        res = [0] * n   #存储结果
        stack = []      #单调栈
        for i in range(n):
            while stack and temperatures[stack[-1]] < temperatures[i]:
                top = stack.pop()
                res[top] = i - top
            stack.append(i)
        return res

以上就是这道题的Python解法。因为这道题本身比较简单,所以有两个需要注意的点往往会被忽略:

  1. 因为最后一天的温度往后没有可以比较的了,所以答案的最后一位一定是 0
  2. 遍历后,stack这个栈内可能还有残留,因为这些残留代表这些天中的任何一天之后都没有能够比该天温度高的日子了,所以这些天的结果都是 0

以上两点在别的题目其实需要考虑到,但是在本题可以不考虑了。

大明白

2021/11/03  阅读:25  主题:默认主题

作者介绍

大明白