1. 先搞清楚题目到底在问什么如果你刷过 LeetCode大概率经历过这种情况做完了 84. Largest Rectangle in Histogram觉得自己掌握了单调栈然后信心满满地点开 85结果被这题按在地上摩擦。说实话我当初做 85 的时候也卡了很久不是因为不会单调栈而是没想明白怎么把“二维矩阵”转化成“一堆柱状图”来解。今天这篇就专门把这道题拆开讲透从暴力思路到最优解代码、推导、踩坑全给你安排明白。85. Maximal Rectangle 这道题的核心需求是给定一个仅包含0和1的二维矩阵找出只包含1的最大矩形面积并返回这个面积值。这里有个容易忽略的细节——矩阵里的元素是字符0/1不是整数 0 / 1。我第一次写的时候直接用matrix[i][j]做加法结果把所有字符的 ASCII 码加一起去了输出一个莫名其妙的数字。这种细节不是题目难是审题不仔细放在面试现场非常减分。那这题适合谁练适不适合新手如果你刚学会 84 题适合刚好检验你是不是真的理解了单调栈还是只是背了代码如果你做过了 84但看 85 完全没思路也适合这篇文章会告诉你两者之间的桥到底怎么搭如果你只是想应付周赛或者面试高频题更适合因为 85 是经典的“柱状图推广到矩阵”的套路题这个转化思路在很多题里都能复用。这道题在 LeetCode 上的标签是数组、动态规划、栈、矩阵难度是Hard但说实话它并没有特别高不可攀的算法难就难在你怎么把二维问题降维成一维问题。一旦想通了这个点代码量其实很小核心代码二十行以内可以写完。下面我用最直白的方式把从暴力到最优的整条路线走一遍。2. 从暴力解开始理清问题的“朴素”边界2.1 暴力枚举的两种思路暴力解永远是理解题意的第一站。对这道题最直观的暴力策略一般有两种策略一枚举矩形的左上角和右下角你随便选两个点一个作为左上角(r1, c1)一个作为右下角(r2, c2)然后检查这个矩形区域里是不是全为1。如果是就更新最大面积。这个做法的复杂度是O(m^3 n^3)级别的因为枚举两个点需要O(m^2 n^2)检查矩形内部是否全 1 还需要O(mn)三个乘起来直接爆炸只能用来验证题意跑测试样例都费劲。策略二固定矩形的高枚举底边的起点和终点假设矩阵有m行、n列你固定一行作为矩形的底边bottom然后从这一行往上数数每一列连续1的高度height[c]。接下来在底边上枚举左边界c1和右边界c2取这个区间内最小的height作为矩形的高度面积就是(c2 - c1 1) * min(height[c1..c2])。这个做法能跑复杂度大约是O(m * n^2)如果m和n都不大比如 50 以内勉强能用。它本质上就是“把每一行当成底边往上构建柱状图”。但我必须说这两种暴力都更适合用来理解题意而不是用来 AC。LeetCode 85 给的数据范围是行列最长 200O(m * n^2)在最坏情况下是200 * 200 * 200 8,000,000理论上可能还能跑但如果测试数据再刁钻一点你会非常被动。而且这题真正的考点是“能不能想到用单调栈或者 DP 优化”面试官要看的也不是你会暴力。2.2 为什么暴力不是终点暴力解能让你快速确认“我理解题目没理解错”但它暴露不出这道题的核心结构。我画个简单例子你感受一下1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0如果只看最后一行作为底边往上统计height得到的高度数组是第 3 行1 0 0 1 0 第 2 行2 0 1 2 1 第 1 行3 0 2 3 2 第 0 行4 0 3 4 3看到没有每一行都能生成一个柱状图。最大矩形一定是“某一行为底边、上面连续 1 构成柱状图里的一个最大矩形”。这个观察非常重要因为它把“二维最大矩形”这个问题拆成了“每一行的柱状图最大矩形”的子问题。而这个子问题正好就是 LeetCode 84 原题。也就是说如果你能高效解出 84那 85 就变成了“跑 m 次 84”。这不是强行套题而是逻辑上本来就成立的分解。3. 关键技巧把二维矩阵按行拆成一维柱状图3.1 高度数组怎么维护先说最常用的做法用一个一维数组heights长度等于矩阵列数n初始全 0。遍历每一行对每个位置j如果当前格子是1heights[j] 1表示这一列向上连续1的高度又高了 1 层如果当前格子是0heights[j] 0表示这一列被“断开”了连续高度直接归零。这个过程不需要额外开二维前缀和一个一维数组滚动更新就够了。每更新完一行就调用一次“柱状图最大矩形面积”的函数取所有行结果的最大值。我用刚才那个矩阵演示一下heights的演变原矩阵: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 处理第 0 行后 heights[1, 0, 1, 0, 0] 处理第 1 行后 heights[2, 0, 2, 1, 1] 处理第 2 行后 heights[3, 1, 3, 2, 2] 处理第 3 行后 heights[4, 0, 0, 3, 0]你看第 2 行处理完heights就是[3, 1, 3, 2, 2]这时候调用 84 题的函数能得到以第 2 行为底的柱状图最大矩形面积是 6第二列高度 1、第三列高度 3、第四列高度 2、第五列高度 2其中条约 3 的高度 2或者别的方式仔细算一下确实能到 6。整体最大值也是 6跟答案一致。所以核心就一句话每一行调用一次“求柱状图最大矩形”的过程取全局最大值。3.2 为什么不能直接二维前缀和有人可能会问能不能直接二维前缀和然后枚举矩形四个边界再用二维前缀和快速判断矩形区域是否全是1理论上可以枚举左上和右下是O(m^2 n^2)每个矩形用前缀和判断是O(1)总复杂度还是O(m^2 n^2)对 200 × 200 的输入大约 16 亿操作在 C 里可能卡着时限过在 Python 里基本不可能。而且这样写完全没有“算法美感”面试官看完会觉得你只会套数据结构的模板。更关键的是这题的考点是“观察结构”不是“暴力加前缀和”。你如果能看出“枚举底边 单调栈”的结构说明你理解了“柱状图”这个抽象层。前缀和的路线虽然可行但它没有利用“连续 1”这个限制条件带来的特殊结构属于杀鸡用牛刀而且牛刀还不好使。4. 三个渐进解法从 O(m²n) 到 O(mn)4.1 逐行枚举底边解法O(m²n)在讲最优解之前我先提供一个比暴力强、但比单调栈弱的过渡方案方便你理解“底边”是怎么枚举的。思路枚举矩形的顶部行top和底部行bottomtop bottom两行之间每一列如果全部是1则这一列可以当作一个“高为bottom - top 1”的柱子把所有满足条件的列连续成区间求最长的连续区间长度乘以高度就是当前top/bottom下的最大矩形面积。这个做法相当于对于每对(top, bottom)把矩阵“压扁”成一个长度为n的数组can[j] 1表示第j列从top到bottom全部是1然后找最长的连续1段。这个找法扫一遍数组即可。复杂度分析top枚举m种bottom枚举m种总共O(m^2)对每对之间计算can[j]需要O(mn)的暴力检查或者用前缀和优化到O(n)得到每一列是否全 1整体最坏O(m^2 n)也就是200 * 200 * 200 8,000,000其实能过但不够漂亮。这个解法的意义在于让你明白“二维最大矩形”实际上可以拆成“选底边区间 数连续有效列的长度”这两个子问题。理解了这个桥再去看单调栈或者 DP 版本会顺很多。下面是前缀和优化后O(m^2 n)的 C 参考实现int maximalRectangle(vectorvectorchar matrix) { if (matrix.empty() || matrix[0].empty()) return 0; int m matrix.size(), n matrix[0].size(); // pre[i][j] 表示第 j 列中前 i 行0-index有多少个连续的 1 vectorvectorint pre(m 1, vectorint(n, 0)); for (int i 0; i m; i) { for (int j 0; j n; j) { if (matrix[i][j] 1) pre[i 1][j] pre[i][j] 1; // 注意这里的“连续”是指从第 i 行往上连续不是历史总和 } } int ans 0; for (int top 0; top m; top) { for (int bottom top; bottom m; bottom) { int len 0; for (int j 0; j n; j) { int ones pre[bottom 1][j] - pre[top][j]; if (ones bottom - top 1) { len; ans max(ans, len * (bottom - top 1)); } else { len 0; } } } } return ans; }代码里pre数组的含义我要再强调一下pre[i][j]存的是从第i行往下到当前行的连续1数量因为遍历时从上往下累加所以表示的是“从第 0 行到第 i-1 行这一列的连续 1 高度”。判断top到bottom这一段列j是不是全1就看这段区间里的 1 的数量是否等于区间长度即pre[bottom1][j] - pre[top][j] bottom - top 1。这个解法虽然复杂度不如最优解但代码非常直白很适合作为“从暴力到优化”的中间态。你要是刚开始刷 Hard强烈建议先把这个版本写出来再优化成单调栈。4.2 最优解思路逐行 单调栈O(mn)接上面第一节的heights数组思路我们现在把“求解柱状图最大矩形”这一步提速到O(n)用单调栈。这就是 85 题最经典的解法也是很多面经里写的最优解。单调栈的核心套路是维护一个单调递增栈栈底到栈顶高度递增遍历每个柱子高度h当当前高度小于栈顶高度时说明栈顶柱子的右边界已经出现可以“结算”它能够扩展到的最大宽度宽度 当前遍历下标到栈中上一个元素下标之间的距离减 1。更具体一点你用一个栈存下标栈内下标对应的高度是递增的。碰到heights[i] heights[stack.top()]说明栈顶那根柱子右边碰到了更矮的墙它无法再向右扩展。于是弹出栈顶记为h新的栈顶就是它左边比它矮的第一根柱子的下标left当前下标i就是右边比它矮的第一根柱子的位置那么宽度就是i - left - 1面积就是h * width。这里有个容易被忽略的点为什么弹出时栈顶的下一个元素就是左边更矮的柱子下标因为栈是单调递增的你弹出当前栈顶后新的栈顶高度一定小于或等于刚才弹出的高度而且它的下标一定在当前弹出下标的左边。这是单调栈的不变性质理解了这一点84 题就通了85 题也只是把这个过程重复 m 次。下面是引入了哨兵在最右和最左都放一个高度为 0 的柱子的标准实现加了哨兵可以避免处理栈为空的边界情况代码会简洁很多int maximalRectangle(vectorvectorchar matrix) { if (matrix.empty() || matrix[0].empty()) return 0; int m matrix.size(), n matrix[0].size(); vectorint heights(n, 0); int ans 0; for (int i 0; i m; i) { // 更新当前行的 heights 数组 for (int j 0; j n; j) { if (matrix[i][j] 1) heights[j]; else heights[j] 0; } // 复制一份并加入左右哨兵避免讨论栈空 vectorint h(n 2, 0); for (int j 0; j n; j) h[j 1] heights[j]; stackint st; st.push(0); // 左哨兵下标 for (int j 1; j n 2; j) { while (h[st.top()] h[j]) { int height h[st.top()]; st.pop(); int left st.top(); int width j - left - 1; ans max(ans, height * width); } st.push(j); } } return ans; }这段代码我非常推荐你亲手敲一遍而不是复制粘贴。因为你在敲的过程中会自然注意到几个关键点哨兵h[0] 0和h[n1] 0的作用左哨兵保证栈不会为空右哨兵保证遍历到末尾时能把栈里所有柱子强制弹出并结算。没有右哨兵你需要在循环结束后再单独处理栈中剩余元素非常容易漏。**while循环的条件是不是**你可以用也没错因为高度相等时先弹出的结算结果不影响最终最大值但用会让栈内元素重复多一些而用会让每个高度相同的柱子逐个结算两种写法都能过。我个人习惯用语义上更接近“遇到严格更矮才结算”。每一行都要重新复制一份带哨兵的数组我的示例代码每次循环都复制其实有点浪费空间但n最多 200这点开销可以忽略。如果你追求极致不需要复制直接在heights上操作单独处理边界即可。面试时写带哨兵的版本目标是快速、正确。4.3 动态规划解法用三个数组记录边界O(mn)除了单调栈LeetCode 官方还经常提到一种heightleftright的 DP 解法。这个解法的思路是从“最大矩形边界”的角度切入height[j]当前行往上列j连续1的高度left[j]在height[j]的这个高度下矩形左边界能扩展到的最左位置right[j]在height[j]的这个高度下矩形右边界能扩展到的最右位置1开区间。每行更新完三个数组之后对第j列能形成的最大矩形面积就是(right[j] - left[j]) * height[j]。维护left和right是这题最容易糊涂的地方我展开讲讲left[j]的更新规则是从左往右扫维护一个curLeft初始为 0。遇到1left[j] max(left[j], curLeft)遇到0left[j] 0curLeft j 1因为下一个可能成为左边界的位置至少是j1。right[j]的更新规则是从右往左扫维护一个curRight初始为n。遇到1right[j] min(right[j], curRight)遇到0right[j] ncurRight j右边边界最远只能到j。这里的max和min都体现了“取每一列在当前高度的约束下边界受到左侧和右侧障碍物的影响逐步收窄”的过程。直接用代码说话C 实现int maximalRectangle(vectorvectorchar matrix) { if (matrix.empty() || matrix[0].empty()) return 0; int m matrix.size(), n matrix[0].size(); vectorint height(n, 0), left(n, 0), right(n, n); int ans 0; for (int i 0; i m; i) { // 维护 height for (int j 0; j n; j) { if (matrix[i][j] 1) height[j]; else height[j] 0; } // 维护 left int curLeft 0; for (int j 0; j n; j) { if (matrix[i][j] 1) { left[j] max(left[j], curLeft); } else { left[j] 0; curLeft j 1; } } // 维护 right int curRight n; for (int j n - 1; j 0; --j) { if (matrix[i][j] 1) { right[j] min(right[j], curRight); } else { right[j] n; curRight j; } } // 结算 for (int j 0; j n; j) { ans max(ans, (right[j] - left[j]) * height[j]); } } return ans; }这个版本的复杂度同样是O(mn)空间O(n)。面试时写哪一种我自己的经验是如果你对单调栈非常熟写单调栈如果面试官问“还有没有别的思路”再拿 DP 版本来讲边界维护的过程。能同时说出两种最优解会是一个非常加分的信号。5. 核心细节拆解为什么单调栈能算出柱状图最大矩形5.1 单调栈的结算过程到底在算什么很多人背了单调栈模板但真问他“为什么弹出的时候结算面积是对的”卡住了。我用一个具体例子走一遍假设heights [2, 1, 5, 6, 2, 3]这就是 LeetCode 84 的经典样例。我们往左右各加一个高度 0 的哨兵变成[0, 2, 1, 5, 6, 2, 3, 0]。遍历过程下标 0高度 0入栈栈为[0]下标 1高度 2入栈栈为[0, 1]下标 2高度 1发现heights[1] 2 1弹出下标 1。高度为 2左边更矮的柱子是下标 0右边更矮的柱子是当前下标 2宽度 2 - 0 - 1 1面积2 * 1 2。这个矩形对应原数组下标 1 这一个柱子宽度 1高度 2。接着下标 2高度 1入栈栈为[0, 2]下标 3高度 5入栈栈为[0, 2, 3]下标 4高度 6入栈栈为[0, 2, 3, 4]下标 5高度 2发现heights[4] 6 2弹出下标 4高度 6左边更矮是下标 3右边更矮是下标 5宽度 5 - 3 - 1 1面积 6。接着弹出下标 3高度 5左边更矮是下标 2右边更矮是下标 5宽度 5 - 2 - 1 2面积 10。这就是最大矩形对应原数组下标 2 和 3高度 5宽度 2下标 5高度 2入栈栈为[0, 2, 5]下标 6高度 3入栈栈为[0, 2, 5, 6]下标 7高度 0弹出下标 6、5、2分别结算最终得到最大面积 10。你发现没有每个柱子只在被弹出的时候结算一次面积这次结算的面积是这个柱子“作为矩形高度”时能形成的最大面积。这个结论非常重要任意一个矩形它一定有一个“最低的高度”也就是构成它的柱子中高度最小的那一根。当单调栈处理到某个比它矮的柱子时这根“最低的柱子”会被弹出此时它的左右边界正好就是它两边第一个比它矮的柱子也就是它能撑起的最大宽度。所以所有可能的矩形面积都在弹出的过程中被考虑到了而且每根柱子最多进出栈一次所以总复杂度是O(n)。5.2 这种结构化的复杂度分析该怎么看84 题的单调栈是O(n)85 题对每一行都做一次就是O(m * n)。这个复杂度相对暴力提升是非常明显的暴力枚举矩形四个边界的复杂度和矩阵面积相关越大的矩阵越爆炸单调栈只对“连续”结构进行一次线性扫描把二维问题拆成了一维问题的重复。我在面试中遇到过一个追问“你能说说为什么是 O(mn)而不是 O(m^2 n) 吗”答案是因为我们不是枚举所有可能的底边区间而是固定底边为每一行然后用单调栈在线性时间内求出该行作为底边时柱状图的最大矩形。所以总共只有m次线性扫描每次O(n)合起来O(mn)。5.3 两种最优解怎么选单调栈 vs 动态规划这里我按实际场景给一个选择维度对比项单调栈解法DPheight/left/right解法核心思想利用“弹出结算”的思路找到每根柱子的左右边界显式维护每列在当前高度下的左右可达边界代码难度中需要理解哨兵和栈的单调性中上left/right 的更新很容易混淆面试讲解难度高需要把为什么弹出即结算讲清楚中边界更新的逻辑比较直观边界处理哨兵技巧代码简洁但依赖理解需要三趟扫描逻辑清晰但代码更长适用题型84、85、以及柱状图变种除了矩形还能推广到带权矩阵问题我自己面试的时候更倾向于写 DP 版本因为它每一步都在显式地维护“左边界”和“右边界”面试官更容易跟上思路。但如果你对单调栈理解得非常深写单调栈会显得更“秀”。不管哪个都一定要能徒手推演一个 3×3 的小矩阵跑通整个过程。6. 实操经验手把手 AC 一遍踩坑全记录6.1 完整可运行代码C把前面提到的单调栈版本整理成可以直接提交的完整代码class Solution { public: int maximalRectangle(vectorvectorchar matrix) { if (matrix.empty() || matrix[0].empty()) return 0; int m matrix.size(), n matrix[0].size(); vectorint heights(n, 0); int ans 0; for (int i 0; i m; i) { for (int j 0; j n; j) { if (matrix[i][j] 1) heights[j]; else heights[j] 0; } vectorint heightsWithGuard(n 2, 0); for (int j 0; j n; j) { heightsWithGuard[j 1] heights[j]; } stackint st; st.push(0); for (int j 1; j n 2; j) { while (heightsWithGuard[st.top()] heightsWithGuard[j]) { int h heightsWithGuard[st.top()]; st.pop(); int left st.top(); int width j - left - 1; ans max(ans, h * width); } st.push(j); } } return ans; } };这段代码在 LeetCode 上提交时间和空间都能击败相当一部分用户。我实测过效率表现很稳定。6.2 Python 版本参考如果你主要用 Python下面是等价的实现需要注意 Python 的stack可以模拟单调栈但建议用list手动维护下标class Solution: def maximalRectangle(self, matrix: List[List[str]]) - int: if not matrix or not matrix[0]: return 0 m, n len(matrix), len(matrix[0]) heights [0] * n ans 0 for i in range(m): for j in range(n): if matrix[i][j] 1: heights[j] 1 else: heights[j] 0 h [0] heights [0] stack [0] for j in range(1, n 2): while h[stack[-1]] h[j]: height h[stack[-1]] stack.pop() left stack[-1] width j - left - 1 ans max(ans, height * width) stack.append(j) return ansPython 要注意一点LeetCode环境里List需要从typing导入否则本地跑可能报错。提交到平台时通常已经内置但本地测试请自行加上。6.3 必踩的坑我当年犯过的错误清单第一坑字符和数字混用。矩阵元素是1不是1直接用int(matrix[i][j])转换没问题但忘了转换直接相加结果全错。这个真的不是段子我见过不止一个人犯。第二坑heights数组更新时忘了归零。遇到0时要把heights[j]重置为 0否则会把前面的高度继续带到下一行导致矩形“穿过”了 0这是原则性错误。你可以试一下不归零答案会偏大。第三坑单调栈弹出时用还是。我用栈内会保留高度相同的柱子结算时有些高度为 0 的会被提前弹出但结果正确。如果用逻辑上等价但要注意代码里while循环别漏写。关键是你要知道自己用的是哪种别混着写。第四坑哨兵数组和原heights下标偏移。我的实现里把heights复制到h下标整体 1就是为了让左哨兵在下标 0。如果不复制直接用heights套哨兵你会被下标偏移搞疯。这个偏移本身不算难但调试时非常容易错。第五坑矩阵为空。输入可能是[]或者[[]]必须在开头判空。漏了判空后面访问matrix[0]直接报错。这个属于基础但高频的错误。第六坑ans初始化为 0 没问题但别初始化成无穷小。因为面积最小也是 0没有全 1 矩形初始化为 0 就够了。初始化成INT_MIN反而会导致没有矩形时输出负数。6.4 现场排查建议如果你本地跑了结果不对我建议按下面这个顺序排查打印每一行更新后的heights数组确认高度积累逻辑对不对对每一行单独用 LeetCode 84 的函数测一下看柱状图最大矩形结果是否正确再检查单调栈结算时的width公式是不是j - left - 1最后检查答案有没有漏掉“只取一个单元格”的矩形也就是高度和宽度都为 1 的情况。最有效的调试技巧是找一个 2×3 或者 3×3 的小矩阵手工画出每一行高度再用暴力枚举对照。你只要手工对过一次基本就不会再错了。7. 从这题延伸变体题和实战表现7.1 相关变体最大正方形、最大空矩形、最大子矩阵和LeetCode 里有很多题跟 85 同源刷完 85 再去做这些你会觉得套路非常清晰221. Maximal Square要求最大的“正方形”而不是矩形。这题最经典的解法是动态规划dp[i][j]表示以(i, j)为右下角的最大正方形边长转移方程是dp[i][j] min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) 1如果你已经理解了 85 的“逐行高度”思想可以试一下把每一行当底边、用单调栈求柱状图里的最大正方形面积也能做出来但 DP 更直接。最大全 1 矩阵Maximal Rectangle本身就是面试常客尤其在一线大厂的面经里经常出现。它考的不是你会不会写单调栈而是你能不能从二维问题里抽出“柱状图”这个子结构。同样的套路还能用于“最大空矩形”求全是 0 的矩形——你只需要把0和1的角色互换即可。最大子矩阵和Maximum Submatrix Sum如果矩阵里的值是任意整数要求找一个和最大的子矩阵那通常是枚举行上下边界然后对该区间内的列做 Kadane 算法。这个思路跟 85 题“枚举底边 一维问题”的结构很像但解法内核不同一个是最大子段和一个是柱状图最大矩形。把这些变体串起来刷一遍你会发现 LeetCode 的很多 Hard 并不是孤立的它们共享同一套“降维”的思维模型。7.2 面试实战这题的正确打开方式如果在面试中碰到这题我建议你按下面这个节奏展开先说暴力思路确认题意说出关键观察每一行作为底边向上看可以形成柱状图所以转成 84 题现场写出单调栈版本面试官如果追问再讲 DP 版本的height/left/right维护思路最后分析复杂度强调每根柱子进栈出栈各一次因此每次结算 O(n)。这套流程下来面试官会认为你不仅有代码能力还有抽象建模能力。我自己在模拟面试里用这套路讲这题反馈普遍是“逻辑很清晰”。7.3 个人实操心得刷了这么多题我有一个很深的体会像 85 这种 Hard最怕的不是你写不出代码而是你根本没有“降维”的思维。如果你只刷过一遍题解、背了代码过两个星期再让你写 85你可能连heights数组的更新都会卡住。所以我强烈建议你用“最小化重复”的原则去刷题拿一个小矩阵手动推演完整过程直到你能不假思索地说出“每一行调用 84 题解法”为止。另外如果你已经刷到 LeetCode 热门 100 题系列了85 基本是绕不开的一个关卡。它在“栈”分类里的地位就像是“滑动窗口”里的 76 题一样——你刷懂一道同一类的十道题都会顺畅很多。最后再分享一个小技巧做 85 之前先把 84 彻底吃透。你要做到给一个数组不用调试直接能画出手动模拟单调栈的全过程。如果你觉得 84 还没完全掌握先别急着碰 85否则你会同时纠结两个难点很容易把挫败感都归结于“这题好难”。LeetCode 85 的关键复习清单 1. 每一行更新高度数组遇 0 清零 2. 每行调用一次柱状图最大矩形算法 3. 单调栈单调递增弹栈时结算面积 4. 左右哨兵能极大简化边界处理 5. 复杂度 O(mn)空间 O(n)。我个人的学习顺序是先暴力验证理解再用O(m^2 n)过渡最后熟练O(mn)单调栈和 DP。每一步都跑个小样例整个过程大概两小时就能彻底拿下。希望这篇题解也能帮你少走点弯路。