05 Python+算法 -02 盛最多水的容器接雨水问题

示例题目：

11. 盛最多水的容器

https://leetcode.cn/problems/container-with-most-water

题目：给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

思路：利用相向双指针移动来将短边换成长边，牺牲宽度换宽度，所以需要和前一次的结果来比，是否面积更大了

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

提交完以后发现时间效率很差，只打败了38%左右的人，我先看灵神题解，发现和我的差不多

于是我学习了其他快的解法，主要有以下两个写法：

1.计算出最大高度*左右指针间隔，这意味着无论指针如何移动，都不能再换取到更高的高度，可以直接结束循环

2.当左右指针的高度相同时，可以一起移动

优化后打败了98%的人

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left = 0
        right = len(height)-1
        ans = 0
        h = max(height)
        while left < right:
            area = (right - left) * min(height[left], height[right])
            ans = max(area,ans)
            if area >= h*(right - left):
                break
            if height[left]<height[right]:
                left += 1
            elif height[left]>height[right]:
                right -= 1
            else:
                left += 1
                right -= 1
        return ans

42. 接雨水

https://leetcode.cn/problems/trapping-rain-water

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

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        leftMax = [height[0]]+[0]*(n-1)
        rightMax =[0]*(n-1)+ [height[n-1]]
        ans = 0
        if n == 0:
            return 0
        for i in range(1,n):
            leftMax[i] = max(leftMax[i-1],height[i])
        for j in range(n-2,-1,-1):
            rightMax[j]= max(height[j],rightMax[j+1])
        for k in range(n):
            ans += (min(leftMax[k],rightMax[k]) - height[k])
        return ans

艰难地改出来了，有好几个踩坑的点

1.leftMax和rightMax初始化的时候要注意，我初始化rightMax的时候复制了leftMax，写成rightMax = [height[n-1]]+[0]*(n-1)，会导致索引是n的值一直是0，从而少算接雨水的量

2.leftMax和rightMax的值计算的时候，是要拿前面的最值和height值做比较，我之前写成和height值前后比较了，会严重导致量算少

3.一定要注意索引

然后这样是写出来了，但是时间效率很差，只打败了19%的人

更好的办法是直接用一次循环解决，相向双指针，时间复杂度 O(n)，空间复杂度 O(1)

因为当左边比右边低的时候，能接的雨水量就是左边最大-高度，右边同理

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

课后作业：

125. 验证回文串

https://leetcode.cn/problems/valid-palindrome

题目：如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。

这个是我自己解出来的哈哈，感觉简单题还是好拿捏一点，不过还是有知识点补充：

1.怎么去除非数字字母字符并小写？--cleaned = ''.join(ch.lower() for ch in s if ch.isalnum())

打败了55%的人，空间复杂度O(1),时间复杂度是O(N)

class Solution:
    def isPalindrome(self, s: str) -> bool:
        cleaned = ''.join(ch.lower() for ch in s if ch.isalnum())
        j = len(cleaned) -1
        i = 0
        while i < j:
            if cleaned[i] == cleaned[j]:
                i += 1
                j -= 1
            else:
                return False
        return True

大神解法，用切片三两句就解决了，确实只要翻转以后相等，不用指针来遍历了

class Solution:
    def isPalindrome(self, s: str) -> bool:
        s = ''.join(ch.lower() for ch in s if ch.isalnum())
        return s == s[::-1]

2105. 给植物浇水 II

https://leetcode.cn/problems/watering-plants

题目：你打算用一个水罐给花园里的 n 株植物浇水。植物排成一行，从左到右进行标记，编号从 0 到 n - 1 。其中，第 i 株植物的位置是 x = i 。x = -1 处有一条河，你可以在那里重新灌满你的水罐。

每一株植物都需要浇特定量的水。你将会按下面描述的方式完成浇水：

按从左到右的顺序给植物浇水。
在给当前植物浇完水之后，如果你没有足够的水完全浇灌下一株植物，那么你就需要返回河边重新装满水罐。
你不能提前重新灌满水罐。

最初，你在河边（也就是，x = -1），在 x 轴上每移动 一个单位 都需要一步。

给你一个下标从 0 开始的整数数组 plants ，数组由 n 个整数组成。其中，plants[i] 为第 i 株植物需要的水量。另有一个整数 capacity 表示水罐的容量，返回浇灌所有植物需要的步数。

class Solution:
    def wateringPlants(self, plants: List[int], capacity: int) -> int:
        n = len(plants)
        step = 0
        water = capacity
        for i in range(n):
            if water < plants[i]:
                step += 2*i
                water = capacity
        
            water -= plants[i]
            step += 1
        return step

我踩了雷，因为我写的是，这样会导致装满水以后没有浇水

        for i in range(n):
            if water < plants[i]:
                step += 2*i+ 1
                water = capacity#加上water -= plants[i]就可以
            else:
                water -= plants[i]
                step += 1

#算法##Python#