每日一题-单调栈

目录

接雨水

---

接雨水

• 时间：0728
• 题目

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

• 思路
  • 本题通过单调栈的思路进行解题
  • 首先，保持栈内单调递减的顺序，当出现后面的元素值超过栈顶元素的值时，就形成了一个“坑”，坑的体积就是左右两侧更矮的墙*两面墙的间距。
  • 循环的结构要采用while，因为比如是20103，当计算完“103”这个坑的时候，还需要计算前面“213”这个坑，当出现更高墙的时候需要将之前的坑的面积都累加到体积中。
• 代码：

public int trap(int[] height) {
        if(height == null || height.length == 0)
            return 0;
        Stack<Integer> stack = new Stack<>();
        int sum = 0;
        for(int i = 0; i < height.length; i ++){
            // 注意这里是while循环
            while(!stack.isEmpty() && (height[i] > height[stack.peek()])){
                int k = stack.pop(); //柱子的底子
                if(stack.isEmpty())
                    break;
                int j = stack.peek(); //此时的左边界
                sum += (Math.min(height[i], height[j]) - height[k]) * (i - j - 1);
            }
            stack.push(i);
        }
        return sum;
    }