【LeetCode 热题 100】84. 柱状图中最大的矩形——（解法一）单调栈+三次遍历
Problem: 84. 柱状图中最大的矩形
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
文章目录
- 整体思路
- 完整代码
- 时空复杂度
- 时间复杂度：O(N)
- 空间复杂度：O(N)
整体思路
这段代码旨在解决一个经典的、难度较高的问题：柱状图中最大的矩形 (Largest Rectangle in Histogram)。问题要求在一个由非负整数组成的数组（代表柱状图）中，找出能勾勒出的最大矩形的面积。
该算法采用了一种非常高效且标准的 单调栈 (Monotonic Stack) 解法。其核心思想是，对于每一个柱子 heights[i]，如果我们能确定以它为最低高度的那个最大矩形的左右边界，我们就能计算出这个矩形的面积。全局的最大面积，必然是这些以每个柱子为最低高度的矩形面积中的最大值。
算法的整体思路可以分解为以下三个步骤：
-
第一步：为每个柱子找到其左侧第一个更矮的柱子
- 算法使用一个单调栈（从栈底到栈顶，索引对应的柱子高度是单调递增的），并从左到右遍历
heights数组。 - 对于当前柱子
heights[i]，它会不断地从栈顶弹出那些比它高或等高的柱子。 - 当这个过程结束后，栈顶的柱子（如果存在）就是
i左侧的第一个严格比heights[i]矮的柱子。这个柱子的索引被记录在left[i]中。如果栈为空，说明左侧没有比它更矮的柱子，我们将边界记为一个虚拟索引-1。
- 算法使用一个单调栈（从栈底到栈顶，索引对应的柱子高度是单调递增的），并从左到右遍历
-
第二步：为每个柱子找到其右侧第一个更矮的柱子
- 这个过程与第一步完全对称。
- 算法清空单调栈，然后从右到左遍历
heights数组。 - 同样，对于当前柱子
heights[i]，它会找到其右侧第一个严格更矮的柱子，并将其索引记录在right[i]中。如果右侧没有更矮的，边界记为虚拟索引n（数组长度）。
-
第三步：计算最终结果
- 现在，对于每一个柱子
i，我们已经知道了以它为最低高度的矩形的左右边界（分别是left[i]和right[i]）。 - 这个矩形的宽度可以被计算出来，即
width = right[i] - left[i] - 1。 - 其面积就是
area = heights[i] * width。 - 最后，算法遍历所有柱子，计算出以每个柱子为最低高度的矩形面积，并取其中的最大值作为最终答案。
- 现在，对于每一个柱子
这种方法通过两次线性扫描和单调栈，高效地为每个柱子找到了其作为矩形高度时的最大可能宽度，从而在线性时间内解决了问题。
完整代码
class Solution {/*** 计算给定柱状图中最大矩形的面积。* @param heights 代表柱状图中各个柱子高度的数组* @return 最大矩形的面积*/public int largestRectangleArea(int[] heights) {int n = heights.length;// st: 一个单调栈，用于存储柱子的索引。Deque<Integer> st = new ArrayDeque<>();// --- 步骤 1: 查找每个柱子左边第一个更矮的柱子 ---// left[i] 存储 heights[i] 左边第一个比它矮的柱子的索引int[] left = new int[n];for (int i = 0; i < n; i++) {int h = heights[i];// 维护单调递增栈：当栈不为空且栈顶柱子 >= 当前柱子时，弹出栈顶。while (!st.isEmpty() && h <= heights[st.peek()]) {st.pop();}// 此时栈顶即为左侧第一个更矮的柱子。如果栈为空，说明左侧没有更矮的。left[i] = st.isEmpty() ? -1 : st.peek();// 将当前柱子索引入栈st.push(i);}// --- 步骤 2: 查找每个柱子右边第一个更矮的柱子 ---// 清空栈以备复用st.clear();// right[i] 存储 heights[i] 右边第一个比它矮的柱子的索引int[] right = new int[n];for (int i = n - 1; i >= 0; i--) {int h = heights[i];// 同样维护单调递增栈（相对于遍历方向）while (!st.isEmpty() && h <= heights[st.peek()]) {st.pop();}// 此时栈顶即为右侧第一个更矮的柱子。如果栈为空，说明右侧没有更矮的。right[i] = st.isEmpty() ? n : st.peek();// 将当前柱子索引入栈st.push(i);}// --- 步骤 3: 计算最大面积 ---int ans = 0;for (int i = 0; i < n; i++) {// 对于每个柱子i，以它为最低高度的矩形面积为：// 高度: heights[i]// 宽度: 右边界 - 左边界 - 1，即 (right[i] - left[i] - 1)ans = Math.max(ans, heights[i] * (right[i] - left[i] - 1));}return ans;}
}
时空复杂度
时间复杂度：O(N)
- 第一遍扫描 (计算
left数组)：外层for循环遍历N次。内层的while循环虽然看起来可能导致复杂度升高，但由于每个元素的索引最多只会入栈一次、出栈一次，所以所有push和pop操作在整个循环中的总次数是 O(N)。因此，这部分的均摊时间复杂度为 O(N)。 - 第二遍扫描 (计算
right数组)：与第一遍扫描的逻辑和分析完全相同，其时间复杂度也是 O(N)。 - 第三遍扫描 (计算
ans)：这是一个简单的for循环，遍历N次，每次执行 O(1) 的操作。时间复杂度为 O(N)。
综合分析：
算法的总时间复杂度是三次独立的线性扫描的和：O(N) + O(N) + O(N) = O(N)。
空间复杂度：O(N)
- 主要存储开销：算法使用了两个辅助数组
left和right，以及一个栈st。int[] left = new int[n]: 占用了 O(N) 的空间。int[] right = new int[n]: 占用了 O(N) 的空间。Deque<Integer> st: 在最坏的情况下（例如，一个严格递增的heights数组），栈需要存储所有N个索引。因此，栈的空间复杂度为 O(N)。
- 综合分析：
算法所需的额外辅助空间由left数组、right数组和栈共同构成。总的空间复杂度为 O(N) + O(N) + O(N) = O(N)。
参考灵神