接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。

示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/trapping-rain-water

class Solution {
public:
    int trap(vector<int>& height) {
        if(height.size() == 0) return 0;
        int re = 0;
        int h_max= height[0]; // 当还未完成接水前最大的高度和下标
        int i = 0;
        while(i < height.size()) {
            int j = i + 1;
            int next_max_height = 0;
            int next_max_index = -1;
            int h_sum = 0;
            for(; j < height.size(); ++j) {
                // （2）向右边找到第一个大于当前最大高度的位置 
                // （1）或者找一个尽可能高的柱子（右侧可能已经不存在比当前更高的柱子了）
                if(height[j] >= next_max_height) {
                    next_max_height = height[j]; // 保存右侧尽可能高的柱子（尽可能靠右边）
                    next_max_index = j; // 记录该柱子的下标
                }
                if(height[j] > h_max) {
                    next_max_height = height[j];
                    break;
                }
                h_sum += height[j];
            }
            if(h_max == 0) {
                // 初始化的时候
                h_max = next_max_height;
                i = j;
                continue;
            }
            if(j < height.size()) {
                // 找到了右侧更高的柱子
                int len = j - i - 1;
                int temp =  len * h_max;
                // cout<<"Y :: "<<"begin_index = "<<i<<"  end_index = "<<j<<"   sum = "<<temp - h_sum<<endl;
                // cout<<"temp = "<<temp<<"   h_sum = "<<h_sum<<endl;
                re += temp - h_sum;
                h_max = next_max_height;
                i = j;
                
            } else {
                // 右边已经不存在比当前保存的高度更大的高度了
                int len = next_max_index - i - 1;
                int temp = len * next_max_height;
                for(int k = i + 1; k < next_max_index; ++k) {
                   temp -= height[k] ;
                }
                re += temp;
                // cout<<"N :: "<<"begin_index = "<<i<<"  end_index = "<<next_max_index<<"   sum = "<<temp<<endl;
                h_max = next_max_height;
                i = next_max_index;
            }
        }
        return re;
    }
};