42. 接雨水

给定 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

Java代码+详细注释

import java.util.Stack;

public class _42接雨水 {
    public static void main(String[] args) {
        Solution solution = new _42接雨水().new Solution();
        int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
        int trap = solution.trap(height);
        System.out.println(trap);
    }
    class Solution {
        /**
         * 思路：单调栈（栈里面只能单调递增或者单调递减）
         * 1.遇到比栈顶小或等的就进栈
         * 2.遇到比栈顶大的 ： 开始出栈
         * 2.1记录第一个出栈的数字大小，作为底，然后继续出栈
         * 2.2遇到大于底的数字（这样就是一个凹槽），通过下标和数字大小，计算能装多少水
         * 2.3计算后将凹槽左边的数字进栈，然后循环步骤1
         *
         * 如果栈空就将当前数字进栈
         *
         * @param height
         * @return
         */
        public int trap(int[] height) {
            int rain = 0;
            Stack<sud> stack = new Stack<>();
            for (int i = 0; i < height.length; i++) {
                //
                sud right = new sud(height[i], i);
                //1.遇到比栈顶大的元素
                while (!stack.isEmpty() && right.num > stack.peek().num) {
                    //1.1取栈顶元素作为底
                    sud button = stack.pop();
                    //1.2将所有和当前底相等的数字出栈(当前栈是单调栈，所以栈中的数字只会比当前数字大于或者等于)
                    while (!stack.isEmpty() && stack.peek().num == button.num) {
                        stack.pop();//栈顶出栈
                    }
                    //1.3出到现在，如果栈不为空，那么就一定是一个凹槽
                    if (!stack.isEmpty()) {
                        sud left = stack.peek();
                        rain += check(left, button, right);
                    }
                }
                //2.当前位置进栈
                stack.add(right);
            }

            return rain;
        }

        /**
         * 计算能装多少水的方法
         *
         * @param left
         * @param button
         * @param right
         * @return
         */
        private int check(sud left, sud button, sud right) {
            //底 * 高
            return (right.index - left.index - 1)  * (Math.min(right.num, left.num) - button.num);

        }

        class sud {
            int num;
            int index;

            public sud(int num, int index) {
                this.num = num;
                this.index = index;
            }
        }
    }
}

思路

看到这个题目第一时间想到的就是栈（后进先出）。这题用到的东西是单调栈。

• 思路：单调栈（栈里面只能单调递增或者单调递减）
  • 1.遇到比栈顶小或等的就进栈
  • 2.遇到比栈顶大的 ： 开始出栈
  • 2.1记录第一个出栈的数字大小，作为底，然后继续出栈
  • 2.2遇到大于底的数字（这样就是一个凹槽），通过下标和数字大小，计算能装多少水
  • 2.3计算后将凹槽左边的数字进栈，然后循环步骤1
  • 如果栈空就将当前数字进栈

• 2.2这中情况下就构成了一个凹槽，凹槽才能装水，那么我们就要计算凹槽能装多少水，就需要用到自定义的结构体，同时存储柱子的高度和柱子的下标
  image.png

• 2遍历到下标6的时候，栈里面剩下 2 1 0，下标6的数字1待进栈，那么这个时候形成了一个凹槽，开始出栈，将所有等于底的数字出栈，完了后栈顶为左高，待进栈的数字为右高，最后将待进栈的数字进栈
  以下标5的高度为底，下标4的高度为左高，下标6的高度为右高，计算水容量，完成后栈为2 1 1
  image.png
  完成后栈如下，然后进行上面同样的操作即可
  image.png