题目描述：
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。如下图
上面是由数组 [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***拿到此题，我当时脑子里也没有什么思路，但经过观察，能装水的地方都是凹陷的地方，只要我们找到这个凹陷的位置，以及他们两边的高度，就很容易求出能装多少水
思路：
1.我们从左向右进行遍历的同时，将对应的数组下标索引存入一个栈中，并且栈中的出栈顺序是从大到小的一个递减的由规律的数字，利用这个特点，我们就可以维护一个最小栈。
2.只有当当前索引处的高度比凹陷处高才有可能储存到水，并且储水的高度是由左右两边的高度最小值以及中间凹陷处决定。
3.为什么我这里要实现内循环，主要是为了找到左边的边界，以便求出水的宽度
所以代码实现如下
package com.cxy.stack;
import java.util.Stack;
/**
* 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
* 输入: [0,1,0,2,1,0,1,3,2,1,2,1]
* 输出: 6
*/
public class Trap {
public int trap(int[] height) {
//创建栈用于保存给定的数组的下标值
Stack<Integer> stack = new Stack<>();
//存储返回结果和返回值
int i = 0,res=0;
//遍历整个数组
while(i<height.length){
//内层循环目的是找到多个值之间到底有多长
//如果当前元素的高度大于前面一个，就要进行计算存储的水有多少
//判断的条件是栈不为空，并且当前元素的高度要大于前一个（查找左边界）
while(!stack.isEmpty() && height[i]>height[stack.peek()]){
//取出当前元素的高度
int currentHeight = height[i];
//中间凹陷的索引
int preIndex = stack.pop();
if(stack.isEmpty())break;
//找到中间凹陷处的高度
int centerHeight = height[preIndex];
//中间凹陷处的前一个元素的高度
int preHeight = height[stack.peek()];
//真正能够装水的高度=左右两边高度的最小值 - 中间凹陷的高度
int minHeight = Math.min(currentHeight,preHeight) - centerHeight;
//----------------------上面获取凹陷的高度--------------------------
//----------------------下面获取凹陷的宽度--------------------------
int width = i-stack.peek()-1;
res += width*minHeight;
//取出当前元素的前一个的前
}
//最后要将索引值+1进入下一个循环遍历
stack.push(i++);
}
return res;
}
}
其实还有其他解决方案，例如双指针，一个从左往右寻找最高的位置，一个从右往左找最高；暴力循环求解，动态规划（这个我不太会）
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1371769065@qq.com
