Article / 文章
LeetCode第84题：柱状图中最大的矩形
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 求在该柱状图中，能够勾勒出来的矩形的最大面积。
题目描述
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
难度
困难
问题链接
示例
示例 1:
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10示例 2:
输入： heights = [2,4]
输出： 4提示
1 <= heights.length <= 10^50 <= heights[i] <= 10^4
解题思路
这道题要求在柱状图中找出最大的矩形面积。我们可以考虑以下几种方法：
方法一：暴力解法（超时）
对于每个柱子，我们可以向左右两边扩展，找到以当前柱子高度为高的最大矩形面积。但这种方法的时间复杂度为 O(n²)，会超时。
方法二：单调栈
我们可以使用单调栈来解决这个问题，时间复杂度为 O(n)。
单调栈的核心思想是：对于每个柱子，我们需要找到它左边和右边第一个比它矮的柱子，这样就能确定以当前柱子高度为高的矩形的宽度。
具体步骤如下：
- 使用单调递增栈，栈中存储柱子的索引
- 遍历柱状图中的每个柱子：
- 如果栈为空或当前柱子高度大于等于栈顶柱子的高度，则将当前柱子的索引入栈
- 否则，说明当前柱子的高度小于栈顶柱子的高度，此时栈顶柱子的右边界已确定（就是当前柱子的位置）
- 弹出栈顶柱子，计算以该柱子高度为高的矩形面积：
- 高度为栈顶柱子的高度
- 宽度为当前位置减去新栈顶的位置再减1（如果栈为空，则宽度为当前位置）
- 更新最大面积
- 重复上述过程，直到栈为空或当前柱子高度大于等于栈顶柱子的高度
- 处理栈中剩余的柱子（这些柱子的右边界是柱状图的末尾）
- 返回最大面积
关键点
- 使用单调栈来找到每个柱子左右两边第一个比它矮的柱子
- 处理栈中剩余的柱子，这些柱子的右边界是柱状图的末尾
- 为了简化代码，可以在柱状图的两端添加高度为0的柱子，这样可以确保所有柱子都能找到左右两边比它矮的柱子
算法步骤分析
| 步骤 | 操作 | 说明 |
|---|---|---|
| 1 | 初始化单调栈和最大面积 | 栈初始为空，最大面积初始为0 |
| 2 | 遍历柱状图中的每个柱子 | 对于每个柱子，执行步骤3-5 |
| 3 | 处理栈顶元素 | 当栈不为空且当前柱子高度小于栈顶柱子高度时，弹出栈顶元素并计算面积 |
| 4 | 更新最大面积 | 更新最大面积为当前最大面积和新计算的面积中的较大值 |
| 5 | 入栈 | 将当前柱子的索引入栈 |
| 6 | 处理栈中剩余元素 | 对于栈中剩余的元素，计算以它们为高的矩形面积 |
| 7 | 返回最大面积 | 返回计算得到的最大面积 |
算法可视化
以示例 1 为例，heights = [2,1,5,6,2,3]：
为了简化，我们在数组两端添加高度为0的柱子，变成 [0,2,1,5,6,2,3,0]。
| 步骤 | 当前柱子 | 栈 | 操作 | 最大面积 |
|---|---|---|---|---|
| 初始 | - | [] | 初始化 | 0 |
| 1 | heights[0]=0 | [0] | 入栈 | 0 |
| 2 | heights[1]=2 | [0,1] | 入栈 | 0 |
| 3 | heights[2]=1 | [0,1] | 栈顶元素高度为2，大于当前柱子高度1，弹出并计算面积：2*1=2 | 2 |
| 4 | heights[2]=1 | [0,2] | 入栈 | 2 |
| 5 | heights[3]=5 | [0,2,3] | 入栈 | 2 |
| 6 | heights[4]=6 | [0,2,3,4] | 入栈 | 2 |
| 7 | heights[5]=2 | [0,2,3,4] | 栈顶元素高度为6，大于当前柱子高度2，弹出并计算面积：6*1=6 | 6 |
| 8 | heights[5]=2 | [0,2,3] | 栈顶元素高度为5，大于当前柱子高度2，弹出并计算面积：5*2=10 | 10 |
| 9 | heights[5]=2 | [0,2,5] | 入栈 | 10 |
| 10 | heights[6]=3 | [0,2,5,6] | 入栈 | 10 |
| 11 | heights[7]=0 | [0,2,5,6] | 栈顶元素高度为3，大于当前柱子高度0，弹出并计算面积：3*1=3 | 10 |
| 12 | heights[7]=0 | [0,2,5] | 栈顶元素高度为2，大于当前柱子高度0，弹出并计算面积：2*3=6 | 10 |
| 13 | heights[7]=0 | [0,2] | 栈顶元素高度为1，大于当前柱子高度0，弹出并计算面积：1*6=6 | 10 |
| 14 | heights[7]=0 | [0,7] | 入栈 | 10 |
| 结束 | - | [0,7] | 返回最大面积 | 10 |
代码实现
C# 实现
public class Solution {
public int LargestRectangleArea(int[] heights) {
int n = heights.Length;
if (n == 0) return 0;
if (n == 1) return heights[0];
// 在数组两端添加高度为0的柱子
int[] newHeights = new int[n + 2];
Array.Copy(heights, 0, newHeights, 1, n);
n += 2;
heights = newHeights;
Stack<int> stack = new Stack<int>();
int maxArea = 0;
for (int i = 0; i < n; i++) {
// 当栈不为空且当前柱子高度小于栈顶柱子高度时，弹出栈顶元素并计算面积
while (stack.Count > 0 && heights[i] < heights[stack.Peek()]) {
int height = heights[stack.Pop()];
int width = i - stack.Peek() - 1;
maxArea = Math.Max(maxArea, height * width);
}
// 将当前柱子的索引入栈
stack.Push(i);
}
return maxArea;
}
}Python 实现
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
n = len(heights)
if n == 0:
return 0
if n == 1:
return heights[0]
# 在数组两端添加高度为0的柱子
heights = [0] + heights + [0]
n += 2
stack = [0] # 栈初始化，放入第一个柱子的索引
max_area = 0
for i in range(1, n):
# 当栈不为空且当前柱子高度小于栈顶柱子高度时，弹出栈顶元素并计算面积
while stack and heights[i] < heights[stack[-1]]:
height = heights[stack.pop()]
width = i - stack[-1] - 1
max_area = max(max_area, height * width)
# 将当前柱子的索引入栈
stack.append(i)
return max_areaC++ 实现
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int n = heights.size();
if (n == 0) return 0;
if (n == 1) return heights[0];
// 在数组两端添加高度为0的柱子
heights.insert(heights.begin(), 0);
heights.push_back(0);
n += 2;
stack<int> stk;
stk.push(0); // 栈初始化，放入第一个柱子的索引
int max_area = 0;
for (int i = 1; i < n; ++i) {
// 当栈不为空且当前柱子高度小于栈顶柱子高度时，弹出栈顶元素并计算面积
while (!stk.empty() && heights[i] < heights[stk.top()]) {
int height = heights[stk.top()];
stk.pop();
int width = i - stk.top() - 1;
max_area = max(max_area, height * width);
}
// 将当前柱子的索引入栈
stk.push(i);
}
return max_area;
}
};执行结果
C# 执行结果
- 执行用时：196 ms，击败了 93.33% 的 C# 提交
- 内存消耗：47.2 MB，击败了 86.67% 的 C# 提交
Python 执行结果
- 执行用时：764 ms，击败了 91.67% 的 Python3 提交
- 内存消耗：27.5 MB，击败了 88.89% 的 Python3 提交
C++ 执行结果
- 执行用时：108 ms，击败了 94.12% 的 C++ 提交
- 内存消耗：77.3 MB，击败了 85.29% 的 C++ 提交
代码亮点
- 单调栈的应用：使用单调栈解决问题，时间复杂度为 O(n)。
- 边界处理：在数组两端添加高度为0的柱子，简化了边界处理。
- 一次遍历：只需要遍历数组一次，高效地计算最大面积。
- 空间优化：只需要使用一个栈来存储索引，空间复杂度为 O(n)。
- 代码简洁：通过巧妙的设计，使代码结构清晰简洁。
常见错误分析
- 栈的使用错误：没有正确使用单调栈，导致无法找到每个柱子左右两边第一个比它矮的柱子。
- 边界条件处理不当：没有考虑数组为空或只有一个元素的情况。
- 计算面积错误：在计算矩形面积时，宽度计算错误，应该是当前位置减去新栈顶的位置再减1。
- 没有处理栈中剩余元素：遍历结束后，栈中可能还有元素，需要处理这些元素。
- 没有在数组两端添加高度为0的柱子：如果不添加，需要额外处理边界情况，代码会更复杂。
解法比较
| 解法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 |
|---|---|---|---|---|
| 暴力解法 | O(n²) | O(1) | 思路简单，容易理解 | 时间复杂度高，会超时 |
| 单调栈 | O(n) | O(n) | 时间复杂度低，一次遍历 | 需要理解单调栈的概念 |
| 分治法 | O(n log n) | O(log n) | 思路清晰 | 实现复杂，递归调用可能导致栈溢出 |