当前位置：首页 > news >正文

单调栈 | part02

news 2026/5/12 16:55:31

42. 接雨水 - 力扣（LeetCode）

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

public int trap(int[] height) { if (height == null || height.length < 3) return 0; int result = 0; Deque<Integer> deque = new ArrayDeque<>(); deque.push(0); for (int i = 1; i < height.length; i++) { if (height[i] <= height[deque.peek()]) { deque.push(i); } else { while (!deque.isEmpty() && height[i] > height[deque.peek()]) { int index = deque.pop(); if (!deque.isEmpty()) { int left = deque.peek(); int right = i; int h = Math.min(height[left], height[right]) - height[index]; int w = right - left - 1; result += h * w; } } deque.push(i); } } return result; }

解题：

这道题的核心在于计算每一列上方能接多少雨水。使用单调栈的方法，主要关注的是横向计算雨水面积。

单调栈的性质：栈中存储的是数组的下标，且这些下标对应的柱子高度是单调递减的（栈底到栈顶）。
触发条件：当遇到一个比栈顶元素高的柱子时，说明形成了一个“凹槽”（由左边界、当前右边界和中间的底部组成），此时可以计算积水量。
计算方式：每次弹出一个栈顶元素作为“底部”，新的栈顶元素作为“左边界”，当前遍历到的元素作为“右边界”。

积水量的计算公式：

底部 (index)：刚刚弹出的元素，它是这一层积水的最低点。
左边界 (left)：弹出index后，现在的栈顶元素。它一定比index高（因为栈是递减的），且是index左边最近的高墙。
右边界 (right)：当前遍历到的i。它比index高（否则不会进入while循环）。
有效高度h：水的高度取决于左右边界中较矮的那个，再减去底部的高度。即min(height[left], height[right]) - height[index]。
有效宽度w：左右边界之间的距离，不包含边界本身，即right - left - 1。

84. 柱状图中最大的矩形 - 力扣（LeetCode）

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

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

1 <= heights.length <=10^5
0 <= heights[i] <= 10^4

public int largestRectangleArea(int[] heights) { if (heights == null || heights.length == 0) { return 0; } //对数组首位加0 int[] nums = new int[heights.length + 2]; nums[0] = 0; nums[nums.length - 1] = 0; for (int i = 1; i < heights.length + 1; i++) { nums[i] = heights[i - 1]; } int result = 0; Deque<Integer> deque = new ArrayDeque<>(); deque.push(0); for (int i = 1; i < nums.length; i++) { if (nums[i] > nums[deque.peek()]) { deque.push(i); } else if (nums[i] == nums[deque.peek()]) { deque.push(i); } else { while (!deque.isEmpty() && nums[i] < nums[deque.peek()]) { int mid = deque.pop(); if (!deque.isEmpty()) { int left = deque.peek(); int right = i; int h = nums[mid]; int w = right - left - 1; result = Math.max(result, h * w); } } deque.push(i); } } return result; }

解题：

我们需要先对原数组进行处理，在首尾加上0，这是为了防止后续栈操作的时候，陷入错误，比如一个递减数组，会一直入栈，而不进行矩阵统计，若是递增数组，会导致后续的元素都无法进入，也无法进行矩阵统计。所以需要加上这俩个值去预防这种问题。

我们的栈与之前的都不同，是一个递增栈，之前都是递减栈。想象你站在中间的一根柱子上（高度为 H ），你要向左右两边拉一条水平的横幅，横幅的高度必须保持在 H 。