暴力双重循环不可行，因其时间复杂度为O(n²)，当n=10⁵时操作量达10¹⁰，必然超时；根本矛盾在于每次扩展右边界都重复计算区间最小值，而单调栈可复用信息，以O(n)线性时间求得每个柱子的左右最近更小下标并完成面积计算。
为什么不能用暴力双重循环
暴力法是枚举每个位置作为矩形左边界，再向右扩展找最小高度，时间复杂度 O(n²)。当 n 达到 10⁵ 时会超时——这不是写法问题，是算法模型本身不可行。
关键矛盾在于：每次向右扩展都要重新扫一遍区间最小值，而这个信息其实可以复用。
单调栈怎么维护“左侧第一个更小”
核心思路是：对每个柱子 heights[i]，快速知道它能向左/右延展多远，直到遇到比它矮的柱子。这等价于求每个下标对应的「左侧最近更小元素下标」和「右侧最近更小元素下标」。
单调递增栈恰好能在线性时间内完成前者：
- 栈中存下标，保证对应高度严格递增
- 当
heights[i]小于栈顶对应高度时，栈顶出栈，此时i就是该栈顶元素的「右侧第一个更小」位置 - 出栈后，新栈顶（若存在）就是它的「左侧第一个更小」位置；若栈空，则左侧可延伸至 -1
示例：heights = [2,1,5,6,2,3]，处理到 i=1（值为 1）时，栈里有 [0]，heights[0]=2 > 1，于是弹出 0，此时左边界是 -1，右边界是 1，宽度 = 1 - (-1) - 1 = 1，面积 = 2 * 1 = 2。
边界处理和哨兵技巧
手动处理边界（如栈空时左边界设为 -1、遍历完后清空栈算右边界为 n）容易漏 case。更稳妥的做法是在原数组两端加哨兵：
- 在
heights前后各插入一个0，变成[0] + heights + [0] - 这样所有原始柱子都一定被弹出过一次，且左右边界自然由两个
0拦住 - 注意遍历时下标要偏移，计算宽度时用
right - left - 1，其中left和right是实际下标
代码片段（关键逻辑）：
vector<int> h = {0};
h.insert(h.end(), heights.begin(), heights.end());
h.push_back(0);
stack<int> st;
int maxArea = 0;
for (int i = 0; i h[i]) {
int idx = st.top(); st.pop();
int w = i - st.top() - 1; // st.top() 此时是左边第一个更小的下标
maxArea = max(maxArea, h[idx] * w);
}
st.push(i);
}
</int></int>
为什么必须用栈而不是双指针或 DP
双指针无法避免回溯：想确定某个位置的右边界，可能得往回跳多次；DP 需要维护每个位置的左右延伸长度，但更新依赖邻接关系，而高度变化不连续，没法用 dp[i] = dp[i-1] + 1 这类简单转移。
单调栈本质是把“等待被更高柱子覆盖”的候选者暂存起来，一旦出现破坏单调性的元素，就批量结算——这是唯一能将每个元素最多入栈出栈一次的结构。
最容易忽略的是：栈中保存的是下标而非高度值；还有清空栈前要确保数组末尾有哨兵，否则最后几个递增柱子永远得不到结算机会。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
