class Solution {
public:/*关键 左边界 height[zuo]>height[zuo+1]右边界 1 是否比height[you]》height[zuo] break;2 不是最后一个 height[you]>height[you-1] && height[you]>height[you+1] 3 最后一个 height[you]>height[you-1] */// 1 失败 找右侧边界 忽略了第一个比自己大的int trap1(vector<int>& height) {int left =0;int right =2;int current=1;int current_i=0;int current_i_cut=0;int current_all=0;for(int i=1;i<(height.size()-1);++i){cout<< i << " "<< " left "<< left << " right "<<right<<" current_all "<< current_all<<endl;current=i;if(height[left]>height[left+1]){right=current+1;bool findright=0;if(right==(height.size()-1)){ // 最后一个右边界findright=1;}if(height[current]<height[right] && height[right] > height[right+1] && (right+1)<height.size()){ // 正常内部的右边界findright=1;}if(findright==1){// 找到右边界current_i_cut=0;for(int j = left+1;j<right;j++) {current_i_cut=current_i_cut+height[j];}current_i= min(height[left],height[right])*(right-left-1);current_all=current_all+current_i-current_i_cut;cout<<"i "<< i << "找到到右边界 "<< " left "<< left << " / "<<height[left]<< " right "<<right << " / "<<height[right]<< " w = "<< (right-left-1) << " h = "<< min(height[left],height[right]) << " current_i_cut "<< current_i_cut << " current_i "<< current_i << " current_all "<< current_all<<endl;current_i_cut=0;current_i=0;left=right;i=left;// cout<<"i "<< i << "找到到右边界 更新数据 "// << " left "<< left << " / "<<height[left]// << " right "<<right << " / "<<height[right]// << " w = "<< (right-left-1) // << " h = "<< min(height[left],height[right]) // << " current_i_cut "<< current_i_cut // << " current_i "<< current_i // << " current_all "<< current_all// <<endl;}else{//current_i_cut=current_i_cut+height[i];// cout<<" 减去i " << i << " 数值 "<< height[i]<<endl;}}else{current_i_cut=0;left=i; }// cout<<"i "<< i << "...最后统计 "// << " left "<< left << " / "<<height[left]// << " right "<<right << " / "<<height[right]// << " w = "<< (right-left-1) // << " h = "<< min(height[left],height[right]) // << " current_i_cut "<< current_i_cut // << " current_i "<< current_i // << " current_all "<< current_all// <<endl;}return current_all;}// 2 通过但是超时int trap2(vector<int>& height) {int left =0;int right =2;int current=1;int current_i=0;int current_i_cut=0;int current_all=0;for(int i=1;i<(height.size()-1);++i){current=i;if(height[left]>height[left+1]){int right=left;int max_num=0;int max_index=0;for(int j=left+1;j<height.size();j++){if(height[j]>max_num){max_num=height[j];right=j;if(max_num>height[left])break; // 只需要找到第一个大的}}current_i_cut=0;int w=right-left-1;int h=min(height[right],height[left]);for(int k=left+1;k<right;k++){current_i_cut=current_i_cut+height[k];}current_i=w*h;current_all=current_all+current_i-current_i_cut;// cout<<"i "<< i << "找到到右边界 更新数据 "// << " left "<< left << " / "<<height[left]// << " right "<<right << " / "<<height[right]// << " w = "<< (right-left-1) // << " h = "<< min(height[left],height[right]) // << " current_i_cut "<< current_i_cut // << " current_i "<< current_i // << " current_all "<< current_all// <<endl;left=right;i=left;}else{left=i; }}return current_all;}// 双指针通过 参考网友思路 官方费解int trap2_shuangzhizhen(vector<int>& height) {/*关于双指针解法，我使用直接比较lmax与rmax的解法，可以AC。我思考了一下，有一个说明其正确性的解释：
由于两个指针都走过了各自的区域，即left指针左边已经遍历，right指针右边已经遍历，因此可以保证lmax和rmax是各自遍历区域内的最大值。因此较小者一定是对应指针所在位置接水时的较低端。
举例说明即：
考虑有lmax<=rmax,此时无论left到right之间的数有多大，left指针位置能接到多少水由lmax决定，因此此时直接统计该位置对答案的贡献是正确的。当lmax>rmax的情况也同理。*/int right=0;int left=height.size()-1;int right_max,left_max=0;int all_water=0;while(right<left){// 当前位置的水 由左右两侧区间的最短边决定。只要找到两侧谁是最短，就可以先决定一侧。right_max=max(right_max,height[right]);// 0-right 区间最大left_max=max(left_max,height[left]); // left-N 区间最大// right - left 区间目前未知，但是左右两侧的最小边，决定了对应左右两侧位置的最小边if(right_max<left_max){ // 右侧最大小于左侧最大// 右侧可以确定，（右侧到左侧中间无论什么情况，左侧最大兜底，右侧不可能在大了）int curent_water=right_max-height[right]; all_water=all_water+ curent_water;//等效all_water += right_max-height[right]right++;}else{// 左侧可以确定，（右侧到左侧中间无论什么情况，右侧最大兜底，左侧不可能在大了int curent_water=left_max-height[left]; all_water=all_water+ curent_water;left--;}}return all_water;}int trap(vector<int>& height) {int right=0;int left=height.size()-1;int right_max,left_max=0;int all_water=0;while(right<left){right_max=max(right_max,height[right]);left_max=max(left_max,height[left]);if(right_max<left_max){int curent_water=right_max-height[right]; all_water=all_water+ curent_water;right++;}else{int curent_water=left_max-height[left]; all_water=all_water+ curent_water;left--;}}return all_water;}};
