盛最多水的容器 接雨水【基础算法精讲 02】

学习B站灵茶山艾府的基础算法精讲 高频面试题合集之(盛最多水的容器 接雨水【基础算法精讲 02】)的总结

11. 盛最多水的容器

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        # 核心思路：相向双指针，最大水量等于两条线的下标差乘以最短高度
        ans = 0
        low, high = 0, len(height)-1
        while low < high:
            ans = max(( high-low ) * min(height[low],height[high]),ans)
            if height[low] < height[high]:
                low += 1
            else:
                high -= 1
        return ans
    
# 跳过无用高度（剪枝优化）
class Solution(object):
    def maxArea(self, height):
        ans = 0
        low, high = 0, len(height) - 1
        while low < high:
            h = min(height[low], height[high])
            ans = max(ans, (high - low) * h)
            
            # 移动矮边，并跳过更矮的（不可能更大）
            if height[low] < height[high]:
                low += 1
                while low < high and height[low] <= h:
                    low += 1
            else:
                high -= 1
                while low < high and height[high] <= h:
                    high -= 1
        
        return ans

小节：用h记录限制面积的高度，用来跳过没用的边

核心思路：相向双指针 + 贪心，面积 (面积等于下标差乘以较短边) 受限于矮边，移动矮边才可能找到更高的边，从而增大面积

优化思路：跳过无用高度的剪枝优化，移动指针后，若新高度不超过之前限制面积的高度，则底边缩短、高度不增，面积必然更小，直接跳过这些无效位置。

42. 接雨水

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        # 方法一：    遍历得到前缀最大高度，后缀最大高度，每一格能接的雨水等于
        #        前缀后缀最大高度的较小值减去当前格的高度
        n = len(height)
        premax = [0] * n
        premax[0] = height[0]
        for i in range(1,n):
            premax[i] = max(premax[i-1], height[i])

        sufmax = [0] * n
        sufmax[-1] = height[-1]
        for i in range(n-2,-1,-1):
            sufmax[i] = max(sufmax[i+1],height[i])
            
        ans = 0
        for h, p, s in zip(height,premax,sufmax):
            ans += min(p,s) - h
        return ans
        
        
class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        # 方法二：    相向双指针，在双指针移动的过程中总是处理较矮的那一边因为
        #        较矮的那一边，它的水位已经被固定了，不会再受另一边更高墙的影响。
        low, high = 0, len(height)-1
        premax, sufmax = 0, 0
        ans = 0
        # 取到等于的原因：
        while low < high:
            premax = max(premax,height[low])
            sufmax = max(sufmax, height[high])
            if premax < sufmax:
                ans += premax - height[low]
                low += 1
            else:
                ans += sufmax - height[high]
                high -= 1
        return ans

小节：

zip() 把多个列表"拉链"到一起，按索引一一对应，同时遍历多组数据时代码更简洁。

a = [1, 2, 3]
b = ['a', 'b', 'c']

zip(a, b)  # 返回迭代器: (1,'a'), (2,'b'), (3,'c')

方法二解法利用了以下关键观察：

左指针 left 和右指针 right：我们分别从数组的两端开始向中间移动。

preMax 和 sufMax：preMax 记录从左边到目前 left 指针所遇到的最高柱子，而 sufMax 则记录从右边到目前 right 指针所遇到的最高柱子。

水位的决定：

• 如果 preMax < sufMax：这表示左边的最高墙（preMax）比右边的最高墙（sufMax）要矮。此时，我们确定 left 指针位置的水位，只取决于 preMax，而与右边的墙无关。因为即使右边还有更高的墙，水位也只能达到 preMax 的高度。
• 如果 sufMax <= preMax：这表示右边的最高墙（sufMax）比左边的最高墙（preMax）要矮或相等。此时，我们确定 right 指针位置的水位，只取决于 sufMax。

简单来说，在双指针移动的过程中，我们总是处理较矮的那一边。因为较矮的那一边，它的水位已经被固定了，不会再受另一边更高墙的影响

核心思路：

方法一：前缀/后缀最大数组,每个位置能接的水量 = min(左侧最大高度, 右侧最大高度) - 当前高度

方法二：相向双指针,从两端向中间移动，总是处理较矮的那一侧。较矮侧的当前水位已被该侧历史最大值"锁定"，不受另一侧更高墙的影响

	方法一	方法二
核心公式	min(左max, 右max) - 当前高度	相同
信息获取	预计算全部前缀/后缀最大	动态维护两侧最大，边移动边更新
空间	O(n)	O(1)
时间	O(n)	O(n)
本质	空间换时间，先存后用	贪心思想，利用单调性省略存储

125. 验证回文串

class Solution(object):
    def isPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        if not s:
            return True
        
        # 筛选字母数字并转为小写
        cleaned = []
        for char in s:
            if char.isalnum():  # 是字母或数字
                cleaned.append(char.lower())
        
        # 判断是否是回文
        return cleaned == cleaned[::-1]
    
# 改进版：内存使用减少
class Solution(object):
    def isPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        if not s:
            return True
        
        # 相向双指针筛选字母数字并转为小写
        low, high = 0 , len(s) - 1
        while low < high:
            while low < high and not s[low].isalnum():
                low += 1
            while low < high and not s[high].isalnum():
                high -= 1
            if s[low].lower() == s[high].lower():
                low += 1
                high -= 1
            else:
                return False   
        return True 

小节：内置函数 str.isalpha()判断是否是字母(注：中文也是字母)；code = ord(char)得到ASCII码，字符串是不可变的。

# 方法2：使用 chr() + ord()，更通用
letters = [chr(i) for i in range(ord('a'), ord('z') + 1)]
# 方法1：使用字符串 + list()
letters = list("abcdefghijklmnopqrstuvwxyz")
print(letters)
# ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 
#  'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']

方法	作用
c.isalnum()	判断字符 c 是否为字母或数字（正是你需要的）
c.isalpha()	判断是否为字母
c.isdigit()	判断是否为数字
s[::-1]	字符串反转
s.upper() / s.lower()	大小写转换

2105. 给植物浇水 II

class Solution(object):
    def minimumRefill(self, plants, capacityA, capacityB):
        """
        :type plants: List[int]
        :type capacityA: int
        :type capacityB: int
        :rtype: int
        """
        count , capa, capb = 0, capacityA, capacityB 
        a , b = 0 , len(plants) - 1
        while a <= b:
            if a == b:
                if capa >= capb and capa < plants[a]:
                    count += 1
                elif capa < capb and capb < plants[a]:
                    count += 1
                break
            if plants[a] > capa:
                count += 1
                capa = capacityA
            capa -= plants[a]
            a += 1
            if plants[b] > capb:
                count += 1
                capb = capacityB
            capb -= plants[b]
            b -= 1

        return count
# 改进版：在while循环外，判断low和high是否相等，代码更简洁
# n为奇数时才会出现low=high
class Solution:
    def minimumRefill(self, plants, capacityA, capacityB):
        ans = 0
        a, b = capacityA, capacityB
        i, j = 0, len(plants) - 1
        while i < j:
            # Alice 给植物 i 浇水
            if a < plants[i]:
                # 没有足够的水，重新灌满水罐
                ans += 1
                a = capacityA
            a -= plants[i]
            i += 1
            # Bob 给植物 j 浇水
            if b < plants[j]:
                # 没有足够的水，重新灌满水罐
                ans += 1
                b = capacityB
            b -= plants[j]
            j -= 1
        # 如果 Alice 和 Bob 到达同一株植物，那么当前水罐中水更多的人会给这株植物浇水
        if i == j and max(a, b) < plants[i]:
            # 没有足够的水，重新灌满水罐
            ans += 1
        return ans

核心思路：相向双指针模拟

设计	说明
i=0 从左往右	Alice 从数组开头向右浇水
j=n-1 从右往左	Bob 从数组末尾向左浇水
a, b	分别记录两人当前水罐剩余水量
水不够就 refill	重新灌满，计数 +1

小节：相向双指针模拟：两人从两端向中间走，各自维护水量，不够就 refill。奇数棵时中间那棵单独判断，由水多的人浇，若都不够只需 refill 一次。核心是将"循环内做太多事"拆分为"循环处理一般情况，循环后处理边界"，使代码更清晰。