# 接雨水

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

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

提示：

# 思路分析：

比如说一开始加入了一个高度为 1 的柱子

然后又加入了高度为 0 的柱子，此时是可以的因为不违反单调的规则

接下来要加入一个高度为 2 的柱子了，此时它违反了单调规则，它要把之前比 2 小的柱子弹出栈

此时弹出栈就意味着此时遇到了一个凹陷的位置了。此时我们就可以去计算雨水的容量了

这些柱子都有 left 和 right 高度，和 i ，j 宽度

那么我们计算雨水的容量就可以通过 j - i - 1 先计算出宽度，然后取最小柱子。然后宽度 * 高度就是当前凹陷区域的雨水容量了，以此类推我们将所以的雨水容量累加起来就是雨水的总容量了

下面通过流程分析，来理解单调栈的解题流程：

首先放入一个高度为 0 的柱子

接下来要放入高度为 1 的柱子了，此时就违反了单调栈的规则了，此时就需要将之前高度为 0 的柱子弹出来。前面说了弹出柱子时我们要计算雨水的容量，但是这种情况下不需要计算，因为弹出高度为 0 的柱子的时候它的左边没有柱子当着。

所以此时只需要将高度为 0 的柱子弹出然后加入高度为 1 的柱子就行了

也就是最左边没有柱子的时候，我们不需要考虑去计算水的容量

然后加入高度为 0 的柱子

再下次加入的时候是高度为 3 的柱子，此时需要将前面两个柱子弹出去

当弹出高度为 0 的柱子的时候就可以根据上面的分析找到它左边的柱子和右边的柱子然后把雨水的容量计算出来

当把高度为 1 的柱子弹出去的时候它左边没有柱子了，也不用计算所以将这个高度为 1 的柱子弹出去然后加入高度为 2 的柱子

下一个加入高度为 1 的柱子

下一个加入高度为 0 的柱子

下一个加入高度为 1 的柱子，此时违反规则弹出高度为 0 的柱子，根据高度为 0 的柱子的左边的柱子和右边的柱子计算出雨水的容量

然后加入高度为 1 的柱子

下一个加入高度为 3 的柱子，此时需要将前面 3 根柱子都弹出去因为都小于 3，在弹出第一根柱子的时候此时这根柱子跟它左边的柱子的高度差是 0 这种情况下不需要考虑雨水，因为它的容量是 0，

然后该弹出第二根柱子的时候它左边的柱子高度是 2 ，此时计算出左边柱子和当前柱子 (3) 中间水的容量

最后高度为 2 的柱子它左边没有柱子了，所以它被弹出后将高度为 3 的柱子加入栈中

下一个加入高度为 2 的柱子

再加入高度为 1 的柱子

下次加入高度为 2 的柱子的时候需要把左边的柱子弹出，此时计算出水的容量然后弹出

下一个加入高度为 1 的柱子，而后续就没有发生高度违反规则的柱子了所以就不存在计算水的容量问题了

其中蓝色的就是水的总容量了

	static class Data
	{
	int height; // 高度
	int i; // 索引
	// 初始化赋值高和宽的值
	public Data(int height, int i)
	{
	this.height = height;
	this.i = i;
	}
	}

	static int trap(int[] heights)
	{
	LinkedList<Data> stack = new LinkedList<>();
	int sum = 0;
	for (int i = 0; i < heights.length; i++)
	{
	Data right = new Data(heights[i], i);
	// 先判断栈是否为空，再判断如果栈中柱子的高度小于当前要加入的柱子高度此时违反了规则就需要弹出小于当前柱子的柱子
	while (!stack.isEmpty() && stack.peek().height < right.height)
	{ // 弹出之前的柱子
	Data pop = stack.pop();
	Data left = stack.peek();
	if (left != null)
	{
	// 当前柱子的索引位置 - 弹出柱子的左边柱子的索引位置 = (差值) 水的宽度计算水的容量
	int width = right.i - left.i - 1;
	// 当前柱子和弹出的左边柱子取最小柱子减去弹出柱子的高度就是水的高度
	int height = Math.min(left.height, right.height) - pop.height;
	// 高 * 宽 = 面积
	// 累加
	sum += width * height;
	}
	} // 当违反规则的柱子弹出完后就继续加入下一个柱子
	stack.push(right);
	}
	return sum;
	}