盛最多水的容器 接雨水【基础算法精讲 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 ans

c++ : 

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;}
};