灵神基础算法精讲-26-学习笔记

单调栈

739. 每日温度

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

思路一：从右到左

把这张折线图想象成一座座山，假设已经遍历完了 6 3 2 5 这四个数，对于比 2 小的数 1 来说，由于 5 的出现，2 绝对不可能是 1 的下一个更大的数，而对于大于等于 2 的数，2 就更不可能是下一个更大的数，所以，由于 5 的出现，2 和 3 永远不可能成为 5 左侧某个数的下一个更大的数，那么就可以把这两个数去掉。

栈中记录下一个更大元素的「候选项」的下标。

每次循环，我们可以在「候选项」中找到答案。

记录数据的时候是加在最上面的，去掉数据的时候也是先从最上面开始，即后进先出，所以用一个栈来维护就好了。

由于在记录一个数之前，会把所有小于等于它的数据都从栈中去掉，所以不可能出现上面大下面小的情况，这说明栈中存储的数据是有序的，所以这个数据结构叫做单调栈。

做法一

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        ans = [0] * n
        st = []
        for i in range(n - 1, -1, -1):
            t = temperatures[i]
            while st and t >= temperatures[st[-1]]:
                st.pop()
            if st:
                ans[i] = st[-1] - i
            st.append(i)
        return ans

时空复杂度分析

每个元素都只会入栈一次，出栈也至多一次，所以出栈的代码至多执行 n 次，所以总的循环次数加起来是 O(n) 的，时间复杂度就是 O(n)，空间复杂度是 O(min(n, U))，U 是数组的最大值减去数组的最小值 + 1

思路二：从左到右

栈里面存储的这些数都还没有找到下一个更大的数，一旦发现了一个比栈顶大的数，就立刻更新栈顶的答案，同时把栈顶元素出栈。

做法二

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        ans = [0] * n
        st = []
        for i, t in enumerate(temperatures):
            while st and t > temperatures[st[-1]]:
                j = st.pop()
                ans[j] = i - j
            st.append(i)
        return ans

总结

及时去掉无用数据，保证栈中数据有序。

42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

思路

横着计算，遍历 5 2 1 0 并记录，下一个遍历到 4 时，可以接水了，接完水之后，前面的坑被填平了，现在只需要记录 5 和 4 就好了，面积由三个下标决定：当前元素的下标、栈顶元素的下标、栈顶下面那个元素的下标。比如 5 2 4 这三个数，5 和 4 的下标之差再减 1 就是宽，5 和 4 的最小值再减去 2 就是高，所以需要同时知道栈顶元素和栈顶下面的元素

做法

class Solution:
    def trap(self, height: List[int]) -> int:
        ans = 0
        st = []
        for i, h in enumerate(height):
            while st and height[st[-1]] <= h:
                bottom_h = height[st.pop()]
                if not st:  # 栈是空的
                    break
                left = st[-1]
                dh = min(height[left], h) - bottom_h  # 面积的高
                ans += dh * (i - left - 1)
            st.append(i)
        return ans

总结

找上一个更大元素，在找的过程中填坑。