网站推广书,社区电商平台排名,龙海市城乡规划建设局网站,开发公司延迟缴纳维修基金申请书目录 题目过程解法 题目
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图#xff0c;计算按此排列的柱子#xff0c;下雨之后能接多少雨水。
过程 发现有特殊情况就是#xff0c;最高峰的地方#xff0c;如果右边小于他#xff0c;然后再右边也都很小的话#xff0c… 目录 题目过程解法 题目
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。
过程 发现有特殊情况就是最高峰的地方如果右边小于他然后再右边也都很小的话并不会存雨水就是两边都要有边界。然后就想了一种思路就是找凹陷。
class Solution {
public:int trap(vectorint height) {int l0;//l和r来保存左右边界int r1;int nheight.size();int room0;//用来存储雨水while(height[l]0){l;rl1;}//找到第一个左边界while(rn){if(height[r]height[l]){//继续搜索凹陷r;}else if(height[r]height[l]){//找到了凹陷计算roomfor(int il1;ir;i){roomheight[l]-height[i];}lr;r;}else{if(r-l1){//如果相邻lr;r;}else{//找到了凹陷计算roomfor(int il1;ir;i){roomheight[l]-height[i];}lr;r;}}}return room;}
};第二个用例对了第一个有问题 应该是右边界的问题如果一直找不到右边等高的那就直接执行完了。没有考虑到局部凹陷的情况。
解法
class Solution {
public:int trap(vectorint height) {int ans 0;int left 0, right height.size() - 1;int leftMax 0, rightMax 0;while (left right) {leftMax max(leftMax, height[left]);rightMax max(rightMax, height[right]);if (height[left] height[right]) {ans leftMax - height[left];left;} else {ans rightMax - height[right];--right;}}return ans;}
};
这个思路就是克服了我上面那个忽略了局部的问题因为我的r也是从左边开始遍历的不可能先遍历到最右边再找有没有边界。r从最右边开始 如果左边小于最右边那么就是假设从左边开始算存雨水的量。因为之前做过一个题是木桶理论存水量取决于短板。所以要从小的一边开始遍历。然后还有两个leftmax和rightmax来保存局部的存水量。因为只要左边小于右边那一定可以存到水。
