算法--接雨水

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

image.png

上面是由数组 [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;
  }
}

其实还有其他解决方案，例如双指针，一个从左往右寻找最高的位置，一个从右往左找最高；暴力循环求解，动态规划（这个我不太会）