接雨水算法 思路讲解与拓展

题目

力扣，42.接雨水

不同思路讲解

思路参考灵神讲解

前后缀分解

思路：我们只需找到当前的height[i]左边最高的柱子以及右边最高的柱子，最后汇总的时候使用公式对于每一个height[i]是否能够接雨水，取决于min(left[i],right[i])-height[i]

我自己写的代码如下：总的来说，代码思路有点混乱，代码可以优化！

class Solution:
    def trap(self, height: List[int]) -> int:
        # 单调栈的求解考虑不充分，应该求解的是height[i] 左边最高和右边最高的柱子
        # 感觉每个左边和右边都要求解
        # 那么最终如何汇总？对于height[i],左右的min(left[i],right[i])-height[i]
        n = len(height)
        # 当结果是n表示找不到
        # left ,right 存储的是高度
        left = [0] * n
        right = [0] * n
        leftmax = height[0]
        for i in range(1, n):
            if height[i] < leftmax:
                left[i] = leftmax
            leftmax = max(height[i], leftmax)
        rightmax = height[n-1]
        for i in range(n - 2, -1, -1):
            if height[i] < rightmax:
                right[i] = rightmax
            rightmax = max(height[i], rightmax)
        ans = 0
        for i in range(n):
            if left[i] == 0 or right[i] == 0:
                continue
            ans += min(left[i], right[i]) - height[i]
        return ans 

灵神的代码：这个pre_max的定义和suf_max的定义，就十分巧妙，可以使用到动态规划，还要注意到初始值的设置

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        pre_max = [0] * n  # pre_max[i] 表示从 height[0] 到 height[i] 的最大值
        pre_max[0] = height[0]
        for i in range(1, n):
            pre_max[i] = max(pre_max[i - 1], height[i])

        suf_max = [0] * n  # suf_max[i] 表示从 height[i] 到 height[n-1] 的最大值
        suf_max[-1] = height[-1]
        for i in range(n - 2, -1, -1):
            suf_max[i] = max(suf_max[i + 1], height[i])

        ans = 0
        for h, pre, suf in zip(height, pre_max, suf_max):
            ans += min(pre, suf) - h  # 累加每个水桶能接多少水
        return ans

单调栈思路

相比于上面的前后缀分离是竖着计算面积，这个单调栈是横向计算面积，相对来说，难一点理解

class Solution:
    def trap(self, height: List[int]) -> int:
        # 单调栈也可以做，边找边计算，对于当前的height[i] > height[st[-1]]的时候
        # 将栈顶弹出，如果栈还有元素，那么该元素是大于我们刚刚弹出的栈顶的
        # 有大小关系  height[st[-1]] < bottom_h  ,bottom_h < height[i]
        n = len(height)
        ans = 0
        st = []
        for i in range(n):
            while st and height[i] > height[st[-1]]:
                bottom_h = height[st.pop()]
                if not st :
                    break
                left = st[-1]
                # 填坑
                ans += (min(height[left],height[i]) - bottom_h)*(i-left-1)
            st.append(i)
        return ans