文章目录
柱状图问题是一道经典的算法题，要求找到能勾勒出的最大矩形面积。暴力解法需要 O(n²) 的时间复杂度，而单调栈技巧可以优化到 O(n)。本文将深入剖析两种单调栈解法，带你彻底掌握这一重要数据结构。
问题描述：柱状图中最大的矩形（力扣 84）
暴力解法
只看题目，不看数组大小范围的话，我们最容易想到的解法就是暴力解法了。
思路分析
最直观的解法就是对于每个柱子，枚举以它（高度）为基准的矩形。
- 对于每个柱子
i，以其高度heights[i]作为矩形高度 - 向左扩展，找到第一个高度小于
heights[i]的柱子位置left - 向右扩展，找到第一个高度小于
heights[i]的柱子位置right - 计算矩形宽度：
width = right - left - 1 - 计算矩形面积：
heights[i] * width - 在所有面积中取最大值
代码实现
代码十分直观，应该都能看懂。
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int n = heights.size();
int ans = 0;
// 遍历每个柱子，以当前柱子为高度计算最大矩形
for (int i = 0; i < n; ++i) {
int left = i;
// 向左寻找第一个高度小于当前柱子的位置
while (left > 0 && heights[left - 1] >= heights[i]) {
left--;
}
int right = i;
// 向右寻找第一个高度小于当前柱子的位置
while (right < n - 1 && heights[right + 1] >= heights[i]) {
right++;
}
// 计算面积并更新最大值
ans = max(ans, (right - left + 1) * heights[i]);
}
return ans;
}
};
但很明显，这是会超时的。heights的大小在 105，暴力解法的时间复杂度为 O(n^2^)，而一般单题的限制在 1s 左右，我们得把基本操作的次数控制在 108~109 这个范围。
暴力解法痛点分析
暴力解法的核心操作是对每个柱子重复寻找左右边界。例如，当处理第 i 个柱子时，需要从 i 向左逐个比较找到 left[i]，再从 i 向右逐个比较找到 right[i]。在这个过程中，存在大量重复比较：比如计算 i+1 的左边界时，可能会再次比较 i 与 i-1 的高度，而这在计算 i 的左边界时已经做过。
这种重复比较导致时间复杂度达到 O(n²)，当 n 较大时效率极低。因此，优化的关键在于减少重复比较，将边界信息的获取从 “每次重新搜索” 改为 “一次遍历中动态维护”。
关键观察：边界的单调性
以左边界为例，观察 left[i]（左侧第一个比 heights[i] 矮的柱子索引）的特性：
- 若
heights[j] ≥ heights[i]（j < i），则j不可能是任何k > i且heights[k] ≤ heights[i]的左边界（因为i更靠右且高度更低）。 - 反之，若
heights[j] < heights[i]，则j可能成为i的左边界，且对于比i更高的柱子，j仍可能作为边界存在。
这意味着左边界的候选集合具有单调性：随着 i 增大，有效候选边界的高度呈现递增趋势（因为高度较高的候选会被更低的新候选取代）。这种单调性为使用栈来维护边界提供了可能。
单调栈的引入：用栈维护有效边界
基于上述观察，我们可以用栈来动态维护左边界的候选集合，具体规则如下：
- 栈中存储柱子的索引，且对应的高度严格递增（即
heights[stack [0]] < heights[stack [1]] < ... < heights[stack [-1]]）。 - 处理
i时，弹出栈中所有高度≥ heights[i]的元素（这些元素不可能成为i或后续柱子的左边界）。 - 弹出后，栈顶元素即为
left[i]（若栈为空，则left[i] = -1）。 - 将
i入栈，作为后续柱子的候选边界。
补充：
当栈为空时，为什么 left[i] = -1？
- 因为我们维护的是左边界即左侧第一个小于
heights[i]的柱子的索引。 - 如果栈为空，说明在柱子
i的左侧没有比它更矮的柱子（因为栈中存储的是递增的柱子索引，栈空意味着当前柱子是遍历到目前最小的，或者左侧没有柱子了）。 - 因此，当栈为空时，-1 指的其实是索引 0 的左侧，即索引 -1（虚拟位置）
- 同理，当我们维护右边界时，如果栈为空，我们将
right[i]设置为n(heights数组的长度)
通过这种方式，每个元素最多入栈和出栈各一次，总操作次数为 O(n)，避免了重复比较。右边界的计算同理，只需反向遍历并维护递减栈即可。
双遍遍历解法：单调栈的基础应用
基于上述推导，我们可以用栈去通过两次遍历，用于维护左右边界数组，再通过计算得出答案：
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int n = heights.size();
vector<int> left(n), right(n); // 存储每个柱子的左右边界索引
stack<int> mono_stack;
// 计算左边界：找到左侧第一个高度小于当前柱子的位置
for (int i = 0; i < n; ++i) {
while (!mono_stack.empty() && heights[mono_stack.top()] >= heights[i]) {
// 栈顶元素高度 >= 当前高度，说明不是左边界，弹出
mono_stack.pop();
}
// 左边界为栈顶或-1（无更小值）
left[i] = (mono_stack.empty() ? -1 : mono_stack.top());
// 当前柱子入栈，为后续柱子提供边界
mono_stack.push(i);
}
// 同理计算右边界：找到右侧第一个高度小于当前柱子的位置
mono_stack = stack<int>();
for (int i = n - 1; i >= 0; --i) {
while (!mono_stack.empty() && heights[mono_stack.top()] >= heights[i]) {
mono_stack.pop();
}
right[i] = (mono_stack.empty() ? n : mono_stack.top());
mono_stack.push(i);
}
int ans = 0;
// 根据左右边界数组计算答案
for (int i = 0; i < n; ++i) {
ans = max(ans, (right[i] - left[i] - 1) * heights[i]);
}
return ans;
}
};
常数优化：一次遍历完成边界计算
虽然双遍遍历效率已经很高了，但我们还可以进一步优化，只需一次遍历就能同时计算左右边界。这种优化的核心是利用元素出栈的时机，同步确定其右边界。
优化的关键依据：出栈元素与当前元素的关系
在计算左边界的遍历过程中，当我们弹出栈顶元素 top 时（因为 heights[top] >= heights[i]），可以观察到一个重要关系：i 是 top 的右边界。
为什么当前元素 i 能够决定出栈元素 top 的右边界呢？
heights[i]是首个在top右侧且高度小于heights[top]的元素（否则top不会被弹出）。- 结合右边界的定义（右侧第一个高度小于当前元素的索引），
i恰好满足right [top] = i。
这意味着，在弹出栈顶元素时，我们可以直接记录其右边界，无需等到反向遍历。
右边界的默认值设定
对于未被弹出的元素（即始终留在栈中的元素），它们的右边界应该是数组末尾 n（因为右侧没有比它们更矮的元素）。因此，我们可以将 right 数组初始化为 n，省去后续处理：
vector<int> right(n, n); // 初始默认右边界为数组末尾
一次遍历的完整逻辑
整合上述发现，一次遍历即可同时计算左右边界：
- 遍历每个元素
i，维护单调递增栈。 - 弹出栈顶元素
top时，同步记录right[top] = i。 - 确定
i的左边界left[i]（栈顶元素或-1）。 - 将
i入栈。
整个过程中，每个元素的左边界在入栈前确定，右边界在出栈时确定（未出栈元素使用默认值 n），实现了一次遍历完成左右边界的计算。
代码实现
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int n = heights.size();
// 常数优化的关键点就在于给 right 数组全部初始化为 n，即默认每个柱子的右边界为数组末尾
vector<int> left(n), right(n, n); // 存储每个柱子的左右边界索引
stack<int> mono_stack;
// 计算左边界：找到左侧第一个高度小于当前柱子的位置
for (int i = 0; i < n; ++i) {
// 当栈不为空且栈顶元素高度>=当前高度时，弹出栈顶元素
// 说明当前i是栈顶元素的右边界（右侧第一个更小的高度）
while (!mono_stack.empty() && heights[mono_stack.top()] >= heights[i]) {
right[mono_stack.top()] = i;
// 栈顶元素高度 >= 当前高度，说明不是左边界，弹出
mono_stack.pop();
}
// 左边界为栈顶或-1（无更小值）
left[i] = (mono_stack.empty() ? -1 : mono_stack.top());
// 当前柱子入栈，为后续柱子提供边界
mono_stack.push(i);
}
int ans = 0;
// 根据左右边界数组计算答案
for (int i = 0; i < n; ++i) {
ans = max(ans, (right[i] - left[i] - 1) * heights[i]);
}
return ans;
}
};
优化后的复杂度分析
- 时间复杂度：仍为
O(n)，但减少了一次遍历，常数项降低。 - 空间复杂度：
O(n)，与双遍遍历相同。
总结：从暴力到单调栈的核心转变
| 阶段 | 核心思路 | 时间复杂度 | 关键优化 |
|---|---|---|---|
| 暴力解法 | 对每个元素重新搜索左右边界 | O(n²) | 无 |
| 单调栈（双遍） | 用栈动态维护边界，减少重复比较 | O(n) | 利用单调性，将边界搜索改为栈内维护 |
| 单调栈（单遍） | 一次遍历中同时计算左右边界 | O(n) | 弹出栈顶时同步更新其右边界，复用遍历过程 |
从暴力到单调栈的推导，本质是对问题中 “边界单调性” 的发现和利用：通过栈这种数据结构，将原本分散的边界信息集中管理，使每个元素的边界信息能在一次遍历中动态确定，从而将时间复杂度从 O(n²) 降至 O(n)。这种思想同样适用于接雨水等类似问题，是算法优化中 “减少重复计算” 的典型范例。
扩展：接雨水问题中的单调栈应用
力扣 42：接雨水
接雨水问题同样可以用单调栈高效解决。接雨水问题描述为：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
接雨水问题中单调栈的使用思路
在接雨水问题中，单调栈存储的是柱子的索引，栈内元素对应的高度是单调递减的。当遇到比栈顶元素更高的柱子时，就意味着栈顶元素处可以形成积水。
具体步骤如下：
- 遍历数组，对于每个元素，当栈不为空且当前柱子高度大于栈顶柱子高度时，弹出栈顶元素。
- 弹出栈顶元素后，若栈为空，则说明没有左边界，无法形成积水，退出循环；否则，计算积水的高度和宽度。积水高度为当前柱子高度与新栈顶柱子高度中的较小值减去弹出元素的高度，积水宽度为当前索引与新栈顶索引的差值减 1。
- 将当前索引入栈。
代码实现
这就不再过多讲解了，直接看代码吧。
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
stack<int> st; // 单调递减栈，存储柱子下标
int ans = 0; // 存储总水量
for (int i = 0; i < n; ++i) {
// 当栈不为空且当前柱子高度大于栈顶柱子高度时
while (!st.empty() && height[i] > height[st.top()]) {
int top = st.top(); // 取出栈顶元素（当前最低洼处）
st.pop(); // 弹出栈顶
if (st.empty()) break; // 栈空说明没有左边界了，退出循环
int left = st.top(); // 新的栈顶是左边界
int width = i - left - 1; // 计算宽度：当前位置与左边界的距离
int h = min(height[i], height[left]) - height[top]; // 计算有效高度
ans += width * h; // 累加当前凹槽的水量
}
st.push(i); // 当前柱子下标入栈
}
return ans;
}
};