前阵子刷洛谷被一道题卡了很久——P1318 积水面积。题目标签明晃晃挂着“栈”但第一次拿到题我完全没往栈上想上来就模拟水位结果把自己绕晕了。后来老老实实把单调栈的思路捋了一遍再回看这道题才发现它把“栈”的精髓讲透了。这篇笔记我整理了小半个月结合我自己踩过的坑给同样在刷信奥赛栈专题的朋友一个参考。这题难度不算高但非常考验对“单调栈结算”的理解深度搞清楚它后面刷接雨水、柱状图最大矩形都会顺很多。1. 拿到P1318题目读进去思路先别急着写代码1.1 题目到底在说什么P1318积水面积简单来说就是给你一排柱子每根柱子宽度为1从左到右排列高度由输入的整数数组表示。柱子之间会有凹下去的坑下雨之后这些坑会积水让我们计算总共积了多少面积。注意这里说的是二维截面每个格子宽度是1高度是整数所以面积可以理解成“水的格子数量”。举个例子高度数组是 [2, 1, 0, 1, 2]这个形状就像一个碗两头高中间低。中间三个位置积水第2个位置高度1水面最高到2水深1第3个位置高度0水面到2水深2第4个位置高度1水深1。总积水面积就是1214。这是最基本的情况大家一眼就能看出来。但问题一旦复杂起来就麻烦了。比如柱子变成 [5, 2, 1, 3, 4, 1, 2, 3]里面有大坑套小坑有平顶有单侧斜坡这时候“肉眼看”就完全不靠谱了必须得有个明确的算法规则。我第一次做这题的想法特别朴素模拟下雨从左往右一格一格扫描看每个位置上有没有左右两侧更高的柱子挡着。这个思路本身没错但实现的时候你会发现一个尴尬的问题——一个位置能不能积水取决于它左边最高的柱子和右边最高的柱子光靠局部信息根本判断不了。于是我开始想有没有一种方法能让我们在处理的过程中“等”到一个合适的时机再结算。1.2 两种常规想法哪条路更配得上“栈”这个标签第一种思路是预处理左右最高值一般叫扫描法。从左往右扫一遍记录每个位置左侧的最大高度 leftMax再从右往左扫一遍记录每个位置右侧的最大高度 rightMax。最后遍历每个位置取 min(leftMax[i], rightMax[i]) 减去当前柱子高度 height[i]如果结果大于0就累加。这个思路非常直观代码也简单时间复杂度 O(n)空间复杂度 O(n)能稳稳通过 P1318 的数据范围。如果你在考场上真的一时想不起单调栈用扫描法绝对不丢分。我最初交过一版扫描法能过而且写得很快大概15分钟就搞定了。但注意这道题的标签是“栈”意思是考察你能不能想到用单调栈来解决。扫描法属于“用空间换思路”而单调栈属于“用玩法换空间”。单调栈不需要额外开两个数组它的精髓在于维护一个栈内元素高度单调递减的结构在出栈的那一瞬间完成积水面积的结算。两种方法结果一样但思考问题的角度完全不一样。1.3 为什么单调栈能成为这类题的通用解想明白这个问题得先理解“积水”产生的过程。一个坑要能积水必须有一个左边界、一个右边界以及中间相对低的底部。也就是说积水本质上是“先降后升”的形状。当你从左往右遍历柱子时上一次看到一个相对高的柱子然后一路下降直到某根柱子突然比之前的柱子高了这时才可能形成坑。这个“后来突然变高”的过程天然适合栈栈可以记录那些“还没等到右边界”的左侧柱子。每遇到一根新柱子如果它比栈顶高就可能让栈顶那根柱子所在的凹槽被“封口”这时候就出栈结算。如果它比栈顶矮那就压入栈等待未来某个更高的柱子来救它。这个思路最早是 leetcode 84 柱状图中最大矩形那一题里讲烂了的但很多人没把它迁移过来。P1318本质上就是“柱状图接雨水”你把这个模型记牢栈专题里一大半的题都能解。labuladong 的刷题笔记里总强调“框架思维”我觉得这题就是活生生的例子单调栈是一种套路但套路得理解着记死背代码没用。2. 单调栈的完整推演从入栈到出栈手把手算一遍2.1 栈里到底存什么下标不是高度写单调栈第一个容易犯糊涂的问题就是——栈里存下标还是存高度很多人直觉是存高度因为后面要比较高度大小。但实际操作下来你会发现只存高度根本没法算面积因为面积不仅取决于高度差还取决于左右边界之间的距离。柱状图中柱子的宽度是1所以面积 高 × 宽宽就是两个边界柱子之间的水平距离这个距离必须用下标差来计算。所以栈里存的是数组下标高度通过 a[stack.top()] 随时可以取到。这个细节看似不起眼但它是整个单调栈算法能不能跑通的关键。第二个问题是栈内元素的单调性。我们要维持一个从栈底到栈顶高度单调递减的栈。也就是说栈顶是当前扫描过的最矮的“待定”柱子越往栈底越高。为什么一定要递减因为一旦出现当前高度大于栈顶高度就意味着栈顶这个位置终于等到了一个比它更高的右边界凹槽可以结算了。如果栈是递增的这个“触发结算”的逻辑就不存在了。这里我多说一句单调栈最重要的是理解“什么时候弹出、弹出之后算什么”。弹出不是目的弹出是为了结算。每次弹出栈顶其实是在结算“以这个栈顶为坑底”的一层积水。2.2 出栈的那一下面积到底怎么算假设现在遍历到下标 i当前高度是 a[i]。当 a[i] 大于栈顶元素对应的高度时栈顶这个下标对应的柱子就是坑底记为 bottom。我们把 bottom 弹出栈然后看看新的栈顶 left。如果栈空了说明 left 不存在也就是说这个 bottom 左边没有比它更高的柱子水会从左边流走不能结算直接跳过。这是很多人容易漏掉的一个判断。如果栈不为空left 就是左侧边界当前 i 就是右侧边界。坑底高度是 a[bottom]左右边界的高度分别是 a[left] 和 a[i]。这层积水能存多高取决于左右边界中较低的那个也就是 min(a[left], a[i])。因为水一旦漫过较低的边界就会流出去所以水面不可能超过这个值。然后关键来了这一层的水深是 min(a[left], a[i]) - a[bottom]宽度是 i - left - 1。为什么宽度不是 i - bottom 或者别的因为 left 和 i 是左右边界两个边界之间的柱子数量才是能蓄水的宽度。bottom 已经被弹出去了但 bottom 所在的这个位置只是坑底的一个点结算时这一层的底面积是整个 left 到 i 之间的区间。最后累加 h * w。有人第一次看到这个公式会晕拿 [2, 1, 0, 1, 2] 这个例子手推一遍就明白了i0栈空下标0入栈。i1a[1]1栈顶 a[0]21 2不触发结算下标1入栈。栈[0,1]i2a[2]00 1不触发结算下标2入栈。栈[0,1,2]i3a[3]11 a[2]0弹出2作为 bottom。栈 [0,1]left1a[1]1a[3]1。h min(1,1) - 0 1w 3 - 1 - 1 1ans 1。然后继续判断1 a[1]1 不成立下标3入栈。栈[0,1,3]i4a[4]22 a[3]1弹出3作为 bottom。栈 [0,1]left1a[1]1。h min(2,1) - 1 0w 4 - 1 - 1 2ans 0。继续判断2 a[1]1弹出1作为 bottom。栈 [0]left0a[0]2a[4]2h min(2,2) - 1 1w 4 - 0 - 1 3ans 3。最终 ans 1 3 4和正确答案一致。注意第二次结算 h0、ans 加的是0这一步看似没用但它在逻辑上保证了等高柱子之间的区域不会有额外积水必须走一遍。这就是单调栈实现时的细节价值。2.3 等高柱子是个坑出栈条件用 还是 这是我在群里看到很多人问的问题出栈循环的判断条件到底是 a[i] a[栈顶] 还是 a[i] a[栈顶]先说结论P1318 两种写法最后答案基本都能对但逻辑细节不同新手建议统一用。为什么因为积水要求严格“左边比坑底高、右边比坑底高”如果左右边界高度和坑底相同那它们之间根本存不住水。用遇到相同高度时不会把栈顶弹出去而是把当前更高或相等的位置压进栈这样可以保证等高柱子作为一个连续平台被保留后续结算时不会被错误拆分。用也可以它会把相等的柱子提前弹出相当于把平台并到右侧新柱子底下最后结算时宽度会变宽高度差不变面积依然正确。但问题是你脑子里模拟的“坑底是谁”容易乱debug 的时候心态容易崩。所以我推荐初学阶段无脑先把逻辑跑通再去研究等号写法的等价性。同样的道理适用于单调队列、单调栈的所有变形题。P1318 是个绝佳的试验田你可以写一版、一版用同一个样例对比输出观察它们路径的差异这对理解单调栈本质特别有帮助。3. 参考代码C 与 Python 各给一版3.1 C 实现带逐行注释信奥赛的主力语言还是 C所以我先给出 C 版本。洛谷支持 C11 以上下面这段代码用 stack 容器配上 vector 存高度清晰度优先。#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorint a(n); for (int i 0; i n; i) { cin a[i]; } stackint st; // 存下标栈底到栈顶高度递减 long long ans 0; // 用 long long防溢出 for (int i 0; i n; i) { // 当前柱子比栈顶高说明可以结算栈顶对应凹槽 while (!st.empty() a[i] a[st.top()]) { int bottom st.top(); st.pop(); // 左边没有更高的柱子水会流走不结算 if (st.empty()) { break; } int left st.top(); int h min(a[i], a[left]) - a[bottom]; int w i - left - 1; ans 1LL * h * w; } st.push(i); } cout ans endl; return 0; }这版代码很短但每一行都有讲究。1LL * h * w是为了防止 int 溢出因为 h 最大可能到 1e5 级别w 也可能到 1e5 级别相乘就是 1e10int 根本装不下。洛谷测试点的数据范围我没仔细查但竞赛题里整数运算溢出是非常经典的失分点宁可多写一步强转。3.2 Python 实现如果你平时用 Python 刷题或者想快速验证思路Python 版更短逻辑完全一样。def trap(height): ans 0 stack [] for i, x in enumerate(height): while stack and x height[stack[-1]]: bottom stack.pop() if not stack: break left stack[-1] h min(x, height[left]) - height[bottom] w i - left - 1 ans h * w stack.append(i) return ans n int(input()) a list(map(int, input().split())) print(trap(a))Python 版本我删掉了类型注解因为洛谷的 Python 评测环境不一定支持较新的语法越兼容越好。这版代码在本地跑和 C 结果一致。3.3 复杂度分析为什么 O(n) 能过不管是扫描法还是单调栈时间复杂度都是 O(n)。扫描法扫两遍数组再加上一遍统计常数大概是3单调栈每个下标最多入栈一次、出栈一次常数大概是1。空间上扫描法需要两个长度为 n 的辅助数组单调栈只需要一个栈最坏情况下栈里存 n 个下标所以空间复杂度也是 O(n)但栈的增长是有弹性的并不会比扫描法差多少。P1318 的数据范围好像是 n 最大到 10000 左右其实 O(n^2) 的暴力也能过一部分点但那样就失去这题的意义了。上考场打竞赛不要因为数据小就乱写养成 O(n) 的思考习惯后面遇到 n1e5、1e6 的题才不会慌。另外提一句如果题目数据变大到 1e5扫描法依然没问题如果变成多组询问、带区间限制那就得上线段树或 RMQ 了但那是另外的课题。P1318 这一步把两种 O(n) 写法吃透就足够应付信奥赛入门组到提高组的常规考察。4. 实战中翻过的车常见错误和排查方法4.1 样例过了交上去全错这是单调栈题最容易遇到的崩溃瞬间。本地样例跑得飞起一提交直接 WA。遇到这种情况先别怀疑人生用最经典的几组特殊数据自测一下。第一组全递增。比如高度 [1, 2, 3, 4, 5]理论上没有积水答案是0。如果你的代码输出负数或者是输出一个莫名其妙的数字赶紧检查是不是在栈空的情况下还在算面积或者出栈后没有判断st.empty()。第二组全递减。比如 [5, 4, 3, 2, 1]理论上也没有积水。很多代码在这组数据上会输出0看起来没问题但如果你的入栈逻辑少了结尾的清理或者循环结束后还在结算栈内剩余元素就会出错。注意 P1318 只要从左往右扫一遍扫描结束后我们不需要清空栈因为剩下的栈元素说明右边没有更高的柱子了它们不可能形成积水。第三组只有一个凹槽。比如 [3, 1, 2]答案是1。这组数据能帮你确认结算公式中的宽度有没有写错。我一开始把宽度写成了i - bottom - 1样例 [2,1,0,1,2] 居然也能过但换到 [3,1,2] 就错了因为 bottom 是坑底的索引用它算宽度会把整个中间区间的大小搞错。正确写法是i - left - 1左右边界之间才是真正的蓄水区间。4.2 边界条件到底哪里边界还有一个常见的坑是输入的第一个位置和最后一个位置永远不可能积水因为积水必须左右都有更高的柱子。很多新手会额外讨论这两个位置其实单调栈天然就处理了。第一个位置入栈时栈空弹出时栈空直接 break最后一个位置如果是高点它会触发前面一系列出栈如果结算后栈空说明它自己作为新边界入栈不会产生额外面积。另外柱子高度可能为0这不算特殊情况0作为坑底也照样结算。真正要小心的是负数——P1318 的柱子高度应该都是非负整数如果读题不仔细有人会默认高度为正数但万一出现0代码也得支持。我的建议是不要对高度做任何额外假设让算法自己处理单调栈天然支持所有非负高度。4.3 一个通用的调试小技巧遇到单调栈题想不通最好的调试方式不是打印最终答案而是打印每次出栈的信息。在 C 代码里临时加上几行输出cout i i bottom bottom left left h h w w ans ans endl;然后用小样例跑一遍观察每次结算的 left、bottom、i 三个下标以及对应的 h、w你会发现单调栈的每一步都在“从左往右找右边界、遇到就结算”。这个过程一旦在脑子里建立起来类似题就不会再出错了。这种调试方法我后来的每道栈题都用可以说是刷题最高性价比的操作。5. 从P1318伸出去栈专题刷题法与竞赛备考提醒5.1 栈专题怎么刷才有效刷题最怕的不是不会而是“看似会了换个马甲又不认识”。栈这个数据结构到了信奥赛里一般会考三类一类是基础的括号匹配、表达式求值一类是单调栈比如 P1318、P5788 单调栈模板、P1901 发射站之类一类是单调队列优化 DP比如 P1886 滑动窗口那是更进阶的内容。我的建议是每做完一道栈题不要急着做下一道先在脑子里把这道题对应的“栈应用场景”提炼出来。P1318 的场景是“等待右边界”P5788 是“寻找下一个更大元素”P1901 是“维护单调递减找左右影响范围”。一旦你发现这些题本质上都在做同一件事——利用栈内元素单调性按某种顺序结算局部答案——你才算真正学会了单调栈。推荐配合 labuladong 那种“刷题笔记”的思维来整理每道题写下数据范围、核心思路、模拟过程、易错点重复三步比无脑刷 100 道题有用得多。我自己整理栈专题的时候P1318 排在最前面因为它足够简单能把单调栈的框架稳稳扎根。5.2 给备考信奥赛的选手两句实在话现在很多省份的复赛线咬得很紧每年都有选手反映就差那么几分非常可惜。栈这个点几乎年年都有机会考到但它往往不会单独出道大题而是作为某个算法的一部分藏在后面。比如图论里非递归 DFS 需要栈表达式求值需要栈计算几何里的凸包算法需要栈。你不把单调栈这种方式内化成肌肉记忆到考场上临时推是推不过来的。还有一点考场上时间宝贵遇到 P1318 这种题我不会第一时间去追求“最优写法”而是先想两种解法的代码量扫描法代码更短单调栈代码也短两者复杂度一样写哪个都行。如果我已经确定栈专题这段时间练得很熟就直接写单调栈如果因为前面题目心态有点乱我会选扫描法保底。这不是能力问题是策略问题。我自己的体会是算法题的“会”分很多层看得懂别人的题解是入门自己能写出 AC 代码是进阶能给别人讲清楚为什么这样写不会错才算彻底掌握了。P1318 积水面积这道题把它用栈的思路讲顺了你会发现栈不再是“后进先出”四个字那么简单——它是一种延迟处理暴力的优雅机制。后面刷题遇到再复杂的结构栈题多想想“我在等什么”答案往往就出来了。
