当前位置：首页 > backend >正文

LeetCode 刷题【42. 接雨水】

backend 2025/8/27 3:34:30

42. 接雨水

自己做

解：双指针左右分割容器

class Solution {
public:int trap(vector<int>& height) {int res = 0;int len = height.size();if(len <= 2)      //构不成一个容器了，直接返回return res;int end = len - 1;        //右边界int start = 0;            //左边界//对左边的边界初始化while(height[start] <= height[start + 1]){    //排除前面部分start++;if(start == end - 1)      //构不成一个容器了，直接返回return res;}//对右边的边界初始化while(height[end - 1] >= height[end]){    //排除后面部分end--;if(end == start + 1)      //构不成一个容器了，直接返回return res;}int left = start + 1;     //左边容器起始int right = end - 1;      //右边容器起始//从左往右靠拢int left_capacity = 0;while(left <= end){if(height[left] < height[start]){ //当遇到比边界小的时，将其看做底，计算当前容器的容量left_capacity += height[start] - height[left];    //累加当前容器的容量}else{                           //当遇到比边界大或者相等时，该容器就封边了，开始找下个容器start = left;                 //新的容器边界res += left_capacity;          //将该容器的容量累加进结果中left_capacity = 0;            //重置容量}left++;                         //延伸容器}//从右往左靠拢int right_capacity = 0;while(right >= start){if(height[right] < height[end]){ //当遇到比边界小的时，将其看做底，计算当前容器的容量right_capacity += height[end] - height[right];    //累加当前容器的容量}else{                           //当遇到比边界大或者相等时，该容器就封边了，开始找下个容器end = right;                 //新的容器边界res += right_capacity;          //将该容器的容量累加进结果中right_capacity = 0;            //重置容量}right--;                         //延伸容器}return res;}
};