2021.4.2

面试题 17.21. 直方图的水量（42. 接雨水）

https://leetcode-cn.com/problems/volume-of-histogram-lcci/

给定一个直方图(也称柱状图)，假设有人从上面源源不断地倒水，最后直方图能存多少水量?直方图的宽度为 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

学到的知识点：单调栈、动态规划、双指针
 一看到这张刻在DNA里的图，我立马就想起了当年大二被一个高二的ACM选手教育啥是单调栈这件事（
 然后拿单调栈写出来了，发现还有两种方法：动态规划和双指针
官方题解
最终代码：（单调栈实现）

public class Solution {
    public int Trap(int[] height) {
        int answer = 0;
        Stack<int> sta = new Stack<int>();//单调递增栈，从栈底到栈顶单调递减
        for (int i = 0; i < height.Length; i++)
        {
            if (sta.Count == 0 || height[sta.Peek()] >= height[i])//栈为空或遇到小于等于栈顶的元素则入栈
            {
                sta.Push(i);
            }
            else
            {
                while (sta.Count > 0 && height[sta.Peek()] < height[i])//遇到大于栈顶的元素则出栈直到可以入栈
                {
                    int tempIndex = sta.Pop();
                    if (sta.Count > 0)
                    {
                        //每次出栈后计算栈顶位置和入栈位置之间可以存的水量
                        answer += (i - sta.Peek() - 1) * (Math.Min(height[sta.Peek()], height[i]) - height[tempIndex]);
                    }
                }
                sta.Push(i);
            }
        }
        return answer;
    }
}