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

今日總結

好耶，寫的第一版代碼直接沒有任何報錯地過了，也是能跑到最優解的程度，今天沒有任何調試，一遍過