【2025-02-06】简单算法：相向双指针盛最多水的容器接雨水

用户11029137

发布于 2025-02-08 14:05:19

4200

代码可运行

文章被收录于专栏：编程学习

运行总次数：0

代码可运行

视频

一，题目汇总
二，视频题目
- 1，11.成最多水的容器
- 2，42.接雨水

一，题目汇总

●视频题目题号： 11，42

二，视频题目

1，11.成最多水的容器

●题目：

●题解：找最大面积：判断什么时候会有更大面积。如果选定了一组边，如图中的红色，则面积由短边决定，且在这组边内的任意一条边与短边的组合不糊再大于原来的面积，因为：当找到更长边时，面积还是由短边决定，但是长变短了。如果找到更短边时，长（x轴）和宽（y轴）都变短了所以，改变短边的指针的指向别的边才可能会产生更大的面积

class Solution:
    def maxArea(self, height: List[int]) -> int:
        max = 0
        i, j = 0, len(height) - 1
        while i < j:
            s = (j - i ) * min(height[i], height[j])
            if s > max:
                max = s
            if height[i] < height[j]:
                i += 1
            else:
                j -= 1
        return max

2，42.接雨水

题目：

题解：对每个长度为一的坑进行单独分析：如果没有柱子，则一个坑能接的水取决于这个坑的前面柱子中的最大柱子和后面柱子中的最大柱子（由短的决定能接的水的数量），即某一个长为一的坑能接水的高度为max（前缀最大值，后缀最大值）如果算上柱子，则减去柱子的柱高就是长度为一的坑的接水量方法一：创建两个额外的数组，用来保存每个坑的前缀和后缀的最大值，每个坑的前缀最大值为：max（上个坑的前缀最大值，该坑高度）

class Solution:
    def trap(self, height: List[int]) -> int:
        ans = 0
        n = len(height)
        pre_max = [0] * n
        suf_max = [0] * n

        # 初始化前后缀最大值的数组
        pre_max[0] = height[0]
        for i in range(1, n):
            pre_max[i] = max(pre_max[i-1], height[i])
        suf_max[-1] = height[-1]
        for i in range(n-2, -1, -1):
            suf_max[i] = max(suf_max[i+1], height[i])

        for h, pre, suf in zip(height, pre_max, suf_max):
            ans += min(pre, suf) - h
        return ans

方法二：双向指针（明确了移动哪一边）分析：因为每个坑能装水的高度是由min(前缀最大值，后缀最大值) - h决定的，所以，我们可以对短边进行计算，计算完后，移动短边到下一个坑代码：

class Solution:
    def trap(self, height: List[int]) -> int:
        ans = 0
        n = len(height)
        left, right = 0, n-1
        pre_max = height[left]
        suf_max = height[right]
        while left <= right:
            pre_max = max(pre_max, height[left])
            suf_max = max(suf_max, height[right])
            if pre_max <= suf_max:
                ans += pre_max - height[left]
                left += 1
            else:
                ans += suf_max - height[right]
                right -= 1
        return ans

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-02-06，如有侵权请联系 cloudcommunity@tencent.com 删除

视频