【4.2】LeetCode每日一题· 直方图的水量

2021年04月02日 11时04分

标签： LeetCode 栈

## 题目描述
给定一个直方图(也称柱状图)，假设有人从上面源源不断地倒水，最后直方图能存多少水量?直方图的宽度为 1。

![](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/10/22/rainwatertrap.png)
上面是由数组 `[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/volume-of-histogram-lcci/ "题目链接")

## 解题思路
这道题很像之前使用**单调栈**求解直方图中最大矩形面积的题目，因此也可以考虑使用**单调栈**求解。

维护一个从栈低到栈顶**单调不增**的栈，其中存放的是直方图中每一个矩形的高。对直方图进行遍历：
1. 如果遍历到的矩形的高小于等于栈顶，则直接将其入栈；
2. 如果当前矩形的高大于栈顶，为了保持栈的单调性，需要重复弹出栈顶元素。此时当前矩形和**栈顶元素的前一个元素**也会围成一个能够装水的区域。
	* 如果**栈顶元素的前一个元素**不存在，那么此时不能装水，直接将其弹出后跳出循环。
	* 否则，设栈顶为`top_height`，对应下标为`top_index`，栈顶元素的前一个元素为`left_height`，对应下标为`left_index`，当前遍历到的矩形下标为i，则有装水区域的长为`i-left_index-1`，高为`min(left_height, height[i]) - top_height`。
	然后将栈顶弹出，继续判断**当前矩形的高是否大于栈顶元素的高**，如果是，则继续重复上述操作，直到**当前矩形的高小于栈顶元素的高**，或者栈为空时，将当前矩形的高压入栈中。

对于一连串的下降序列，因为在计算当前遍历到的矩形和某一直方图矩形围成的容器能接的雨水的体积时，后一个直方图矩形和当前遍历到的矩形所围成的容器能接雨水的体积已经计算过了，因此在计算高的时候需要减去`top_height`。

P.S.: 自己尝试解题的时候虽然想到了使用单调栈，但是想了1个多小时也没有想出正确做法，主要问题是没有考虑到栈顶的前一个元素和当前遍历到的矩阵能够接的雨水的体积，只想着如何使用栈顶元素和当前矩形计算出体积，其实仔细想一想这显然是不对的（**栈顶元素和当前矩形间距为0，怎么可能围住雨水呢？**）。单调栈是一个薄弱的知识点，亟需加强。

### 代码
```cpp
class Solution {
public:
    int trap(vector<int>& height) {
        stack<pair<int, int>> st;
        int bottum = 0, res = 0;
        for(int i = 0; i < height.size(); i++){
            while(!st.empty() && height[i] > st.top().first){
                pair<int, int> top = st.top(); 
                st.pop();
                if(st.empty()){
                    break;
                }
                pair<int, int> left = st.top();
                int w = i - left.second - 1;
                int h = min(left.first, height[i]) - top.first;
                res += w * h;
            }
            st.push({height[i], i});
        }
        return res;
    }
};
```

## 用时和内存
> 执行用时：4 ms，在所有 C++提交中击败了92.99%的用户
> 内存消耗：13.6 MB，在所有 C++提交中击败了53.58%的用户

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【4.2】LeetCode每日一题· 直方图的水量

所有评论

暂无评论

新增评论