盛最多水的容器 接雨水【基础算法精讲 02】
盛雨水最多的容器
链接 :
11 盛最多水的容器
思路 :
双指针 ：
1.对于两条确定的边界，l和r,取中间的线m与r组成容器，如果m的高度>l的高度，那么整个容器的长度会减小，如果低于l的高度，那么不仅高度可能会减小，长度也一定会减小；
2.取l=0,r=n-1，循环遍历答案即可；
代码 (c++):
class Solution {
public:int maxArea(vector<int>& height) {int n = height.size();int i=0,j=n-1,ans=0;while(i < j){ans = height[i] < height[j] ? max(ans, (j - i) * height[i++]): max(ans, (j - i) * height[j--]); }return ans;}
};代码(python) :
class Solution:def maxArea(self, height: List[int]) -> int:ans = 0l = 0r = len(height)-1while l<r:s = (r-l)*min(height[l],height[r])ans = max(ans,s)if height[l] < height[r]:l += 1else :r -= 1return ans接雨水
链接 :
https://leetcode.cn/problems/trapping-rain-water/
思路 :
假设每个位置都是一个宽度为一的桶；
对于每个位置能够存多少水，取决于左边和右边的最大高度；
法一 :
用两个数组来表示 前缀 和 后缀的最大值；
详见代码一
时间复杂度 : O(n)
空间复杂度 : O(n)
法二 :
双指针 :
取l=0,r=n-1;
一边遍历一边更新前缀的最大值pre_max 和 后缀的最大值suf_max!
时间复杂度 : O(n)
空间复杂度 : O(1)
详见代码二
代码 :
代码一 :
python :
class Solution:def trap(self, height: List[int]) -> int:n = len(height)# 前缀最大值数组fs = [0] * nfs[0] = height[0]for i in range(1,n):fs[i] = max(fs[i-1],height[i])# 后缀和最大值数组es = [0] * nes[-1] = height[n-1]for i in range(n-2,-1,-1):es[i] = max(es[i+1],height[i])ans = 0for h , f , e in zip(height,fs,es):ans += min(f,e)-hreturn ans代码二 :
python :
class Solution:def trap(self, height: List[int]) -> int:n = len(height)l = 0r = n - 1ans = 0pre_max = 0suf_max = 0while l<=r:pre_max = max(pre_max,height[l])suf_max = max(suf_max,height[r])if pre_max < suf_max : ans += pre_max-height[l]l += 1else :ans += suf_max - height[r]r -= 1return ansc++ :
class Solution {
public:int trap(vector<int>& a) {int len = a.size();int lmax=a[0],rmax=a[len-1];int l=1,r=len-2;int ans=0;while(l<=r){if(lmax < rmax){ans += max(min(lmax,rmax)-a[l],0);lmax = max(lmax,a[l]);l++; }else{ans += max(min(lmax,rmax)-a[r],0);rmax = max(rmax,a[r]);r--;}}return ans;}
};