单调栈 part02

42. 接雨水

题目描述

给定 n 个非负整数表示每个宽度为 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 个单位的雨水（蓝色部分表示雨水）。

解题思路

class Solution {
    public int trap(int[] height) {
        int ans = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        // 横向求
        for (int i = 0; i < height.length; i++) {
            int h = height[i];
            // 单调递减
            while (!stack.isEmpty() && height[stack.peek()] <= h) {
                int bottomH = height[stack.pop()];
                // 栈空，找不到左边界
                if (stack.isEmpty()) {
                    break;
                }
                // 获取左边
                int left = stack.peek();
                // 获取高度差
                int dh = Math.min(height[left], height[i]) - bottomH;
                // 高 ✖️ 宽
                ans += dh * (i - left - 1);
            }
            stack.push(i);
        }
        return ans;
    }
}

84. 柱状图中最大的矩形

题目描述

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

解题思路

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return heights[0];
        }

        int area = 0;

        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) {
                int height = heights[stack.pop()];

                while (!stack.isEmpty() && heights[stack.peek()] == height) {
                    stack.pop();
                }

                int width;
                if (stack.isEmpty()) {
                    width = i;
                } else {
                    width = i - stack.peek() - 1;
                }

                area = Math.max(area, width * height);
            }
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            int height = heights[stack.pop()];

            while (!stack.isEmpty() && heights[stack.peek()] == height) {
                stack.pop();
            }

            int width;
            if (stack.isEmpty()) {
                width = n;
            } else {
                width = n - stack.peek() - 1;
            }
            area = Math.max(area, width * height);
        }
        return area;
    }
}