政务服务中心 网站建设,网站怎么在微博推广,全国有多少家展馆设计公司,湛江电气建站软件盛雨水最多的容器
链接 :
11 盛最多水的容器
思路 : 双指针 #xff1a;
1.对于两条确定的边界#xff0c;l和r,取中间的线m与r组成容器#xff0c;如果m的高度l的高度#xff0c;那么整个容器的长度会减小#xff0c;如果低于l的高度#xff0c;那么不仅高度可…盛雨水最多的容器
链接 :
11 盛最多水的容器
思路 : 双指针
1.对于两条确定的边界l和r,取中间的线m与r组成容器如果m的高度l的高度那么整个容器的长度会减小如果低于l的高度那么不仅高度可能会减小长度也一定会减小
2.取l0,rn-1循环遍历答案即可
代码 (c):
class Solution {
public:int maxArea(vectorint height) {int n height.size();int i0,jn-1,ans0;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 lr: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)
法二 :
双指针 :
取l0,rn-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[i1],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 lr: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(vectorint a) {int len a.size();int lmaxa[0],rmaxa[len-1];int l1,rlen-2;int ans0;while(lr){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;}
};
