Leetcode42: 接雨水

【题目描述】

image.png

【思路】
思路1： 找左边最大值与右边最大值，取较小值为可达高度。再减去这个位置本来的高度，为积水高度。
对于思路1的优化：
一个数组记录从左到右的最大值，另一数组记录从右到左的最大值
计算时取两者的较小值
不需要每次都遍历 减少了时间复杂度

思路2：
栈
维护一个单调递减的栈
idx对数组进行遍历
①若height[idx]小于栈顶元素 将其idx加入stack
②若height[idx]大于栈顶元素 则出现了凹槽（可积水！）开始我们的计算
pop出栈顶元素 （这时要计算的是pop这个位置上的水柱）
高度为左右两边的较小值
宽度为左右两边减一减

相对于思路1 竖着算每根水柱
思路2是横着算的

【代码】

int trap(vector<int>& height) {
    //Leetcode42:接雨水
    int area = 0;
    stack<int> record;
    int idx = 0;
    while (idx < height.size()) {
        if (!record.empty()) {
            while (height[idx] > height[record.top()]) {
                int p = record.top();
                record.pop();
                if (record.empty()) break; //若栈为空 结束 注意这里的处理 边边上无法积水


                int h = min(height[idx], height[record.top()]) - height[p];
                int dis = idx - record.top() - 1;
                //cout << "h: " << h << endl;
                //cout << "dis: " << dis << endl;
                area = area + h * dis;
                //cout << "area: " << area << endl;
            }
        }

        record.push(idx);
        idx++;
    }
    return area;

}