说实话第一次在题库里刷到“最大宽度坡”这道算法题时我的第一反应是这不就是双重循环遍历所有 (i, j)遇到 A[i] A[j] 就更新一下 j - i 的最大值吗但当我真去提交这个版本时用时直接超到怀疑人生。这道题的标题只有五个字题面也短但它考察的内容却非常典型从暴力枚举到单调栈优化再到排序和二分答案每一步都在逼你重新审视“枚举”这件最朴素的事。这篇文章我会从这道题本身出发完整拆解为什么暴力会挂在数据规模上、单调栈解法是怎么一步步推出来的、排序法和二分宽度法分别是怎么另辟蹊径的以及我在笔试和刷题过程中踩过的边界条件坑。无论你是刚开始刷 LeetCode 的新手还是在准备算法设计与分析期末考试或者是面试前想快速吃透一类单调栈题目的老手这篇都应该能给你一个可以直接“抄作业”的完整思路。1. 先拆题面最大宽度坡到底在求什么1.1 “坡”这个名字到底形象在哪题目原文不长给你一个整数数组 A定义“坡”为一对下标 (i, j)要求 i j 且 A[i] A[j]这个坡的宽度是 j - i。让你返回数组里所有坡中最大的宽度如果不存在满足条件的坡就返回 0。“坡”这个比喻其实很形象。你把数组下标当作横轴坐标数组值当作纵轴高度那 A[i] A[j] 就相当于从左边的低处望向右边的高处视线是向上走或者水平的这就构成了一段“坡”。坡的宽度则是两个点在横轴上的距离题目问的是最远能从哪个低点走到哪个不更低的高点。举个具体例子数组[6, 0, 8, 2, 1, 5]i0, j2A[0]6 A[2]8宽度 2i1, j5A[1]0 A[5]5宽度 4i3, j5A[3]2 A[5]5宽度 2i4, j2 不合法因为 i 必须小于 j。肉眼扫一遍就能发现最优解是从下标 1 到下标 5宽度为 4。这个例子我后面还会反复用到用来验证不同解法。这道题最早出自 LeetCode 962难度标的是中等但它在笔试里的出场率不低。我印象里很多公司的算法卷里都会把它包装成“求两元素之间满足大小关系的最远距离”之类的变体核心结构完全一样只是换了一层皮。理解了原题后面遇到变体才不会慌。1.2 题目规模决定了暴力的命运很多同学看到这种求“最大差值”的题第一反应就是两层 for 循环外层固定左端点 i内层让右端点 j 从 i1 扫到末尾满足 A[i] A[j] 就更新答案。这个思路没有任何问题但它忽略了最致命的一点题目给的数据规模允不允许你枚举所有下标对。如果数组长度 n 在 100 以内暴力解法确实够用。但 LeetCode 原题里 n 会拉到 50000 甚至更高的量级这时候 O(n^2) 意味着最多 2.5 × 10^9 次比较。Python 在 2 秒左右的时间限制下能跑完 10^8 次操作就已经很不错了25 亿次比较基本是稳稳的超时。搞清楚这一点很重要因为很多“算法思维题”考察的不是你会不会写 for 循环而是你能不能从数据规模反推出题目想要的复杂度。看到 n50000基本可以判断正解应该往 O(n log n) 或者 O(n) 去设计。这也是我刷题时养成的一个习惯先看数据范围再决定尝试什么复杂度的解法。2. 暴力解法先实现再优化把“为什么不行”想明白2.1 两层循环版本的三分钟实现先把最简单的暴力版本写出来这不是为了提交而是为了给后面所有优化立一个对照基准。代码很短def max_width_ramp(nums): n len(nums) ans 0 for i in range(n): for j in range(i 1, n): if nums[i] nums[j]: ans max(ans, j - i) return ans内层循环从 i1 开始是因为题目要求 i jans 初始化为 0对应不存在任何坡的情况。这个实现哪怕一个刚学 Python 的人也能看懂但它的问题也很直观n 个元素要两两配对比较次数是 n(n-1)/2。我当初用这个版本直接去跑 LeetCode本地小数据一切正常一提交就超时。测试用例里有一组 n50000 的递增数组我盯着进度条想如果这是一道期末编程题老师让手写这个暴力版本理论上能拿一半分但放到严格限时的在线评测里这个版本就是一张废纸。2.2 从冗余比较里挖出优化方向暴力版本被数据规模判了死刑但如果只是知道“超时”两个字就跳到正解那这道题刷得有点浪费。我习惯回头想一个问题刚才那些比较里有多少是白做的举一个最明显的冗余如果 A[0]10A[1]1那么任何 j 只要能跟 A[1]1 组成坡它一定也能跟 A[0]10 组成坡吗不会因为 10 A[j] 这个条件比 1 A[j] 苛刻得多。反过来看只要 A[1]1 满足条件那用 A[0]10 去比较纯属浪费时间因为用 A[1]1 就能得到更大的宽度下标 1 比下标 0 更靠右相同的 j 下宽度更大。再进一步从左往右扫描时如果当前元素比之前某个元素还要小那么之前那个元素作为左端点的价值就直接清零了。因为你完全可以用当前这个更小、更靠右的元素替代它替代之后同样面对同一个右端点宽度只会更大条件也只会更松。这就是“左端点压缩”的思想雏形那些可能成为最优左端点的候选下标对应的数组值必须从左往右严格递减。也就是你只需要保留下标递增、值递减的一串位置。这个发现正是从暴力解法的冗余比较里自然长出来的。我经常跟人说刷题别直接背题解先把暴力的冗余想明白很多优化思路就是自己的了。这个“更靠右且值更小”的候选左端点集合放在数据结构里恰好就是单调栈的形态。所以下一节我们就沿着这条线索把单调栈解法完整地推一遍。3. 单调栈 反向扫描最优解法的完整推导3.1 左端点候选集只需要保留严格递减的索引刚才我们说了一个元素如果比它前面某个元素大那它作为左端点候选基本没有优势。这里要再补一个细节如果两个元素值相等应该保留哪个假设 A[2]3A[5]3。显然下标 5 比下标 2 更靠右未来无论右端点 j 选在哪儿只要 j 5用下标 5 当左端点得到的宽度一定比下标 2 更大同时 A[5]A[2]值约束完全相同。所以值相等时靠右的元素完胜。这就是为什么我们要用严格递减而不是非严格递减A[i] A[stack[-1]]才入栈等于的情况直接放弃旧候选。用单调递减栈构建候选左端点的代码长这样def build_candidates(nums): stack [] for i in range(len(nums)): if not stack or nums[i] nums[stack[-1]]: stack.append(i) return stack拿[6, 0, 8, 2, 1, 5]手动走一遍i0栈空0 入栈栈为 [0]对应值 [6]i1nums[1]0 61 入栈栈为 [0, 1]对应值 [6, 0]i2nums[2]8 0不入栈i3nums[3]2 0不入栈i4nums[4]1 0不入栈i5nums[5]5 0不入栈。最终候选左端点只有两个下标 0值 6和下标 1值 0。你可能会问下标 2 的 8 虽然比 0 大但它比 6 也大所以确实没资格入栈下标 3 的 2、下标 4 的 1 同理。那么最终候选集合里下标 0 和下标 1 就够了吗答案是够的因为任何能由其他下标做左端点形成的坡都有一个“值更小、下标更靠右”的候选能替代它把宽度拉得更大。3.2 右端点从右往左扫为什么可以放心 pop有了候选左端点集合接下来要确定右端点。直觉上会想从右往左扫描 j因为最大的宽度一定来自尽可能靠右边的右端点而候选左端点都在栈里。扫描过程中如果发现nums[stack[-1]] nums[j]说明栈顶这个左端点和当前 j 能组成坡于是更新答案。关键问题来了更新完答案之后要不要 pop 栈顶很多第一次学这个解法的人会卡在这里——左端点还有用吗后面 j 继续向左移动时宽度一定变小因为 j 在变小而同一个左端点的下标不变。哪怕后面还能遇到满足条件的右端点得到的 j - stack[-1] 也不可能比当前 j - stack[-1] 更大了。所以这个栈顶左端点已经不可能再产生更优解可以放心 pop。换句话说右端点从右往左扫是为了让每个弹出的左端点只被处理一次把复杂度压到 O(n)。这也是“反向扫描”的核心意义。如果从前往后扫右端点你会发现一个左端点可能要在多个 j 处被重复考虑既浪费时间又很难在弹出时给出安全的理由。整体代码def max_width_ramp(nums): n len(nums) if n 2: return 0 stack [] for i in range(n): if not stack or nums[i] nums[stack[-1]]: stack.append(i) ans 0 for j in range(n - 1, -1, -1): while stack and nums[stack[-1]] nums[j]: ans max(ans, j - stack.pop()) return ans从右往左扫到 j5nums[5]5栈顶是下标 1nums[1]0 5更新 ans4弹出 1新的栈顶是下标 0nums[0]6 5不满足条件继续向左。到 j2nums[2]8栈顶下标 06 8更新 ans2弹出。整个过程结束答案 4正确。3.3 Python 代码与复杂度分析这段代码的时间复杂度是 O(n) 的构建栈时每个下标最多入栈一次反向扫描时每个下标最多出栈一次整体循环是线性的。空间复杂度 O(n)因为最坏情况下数组整体严格递减栈里要装下 n 个下标。我实际跑下来这个版本在 LeetCode 962 的测试数据里表现非常稳5 万长度的数组基本毫秒级返回。这也是面试官最想看到的解法最优复杂度、思路清晰、代码量少。提示写代码时不要忘了处理 n 2 的情况否则有些解法里初始化变量会出问题。虽然这道题数据范围通常保证有长度但养成防御性习惯不亏。4. 换条路走排序法和二分宽度法4.1 排序下标法用一维顺序同时满足两个约束单调栈是这道题最经典的解法但面试里如果你能再补充一两种思路会显得你真的理解了问题的本质而不是背题。排序下标法就是很值得掌握的替代解法。思路是这样坡有两个约束一个是值的大小关系 A[i] A[j]另一个是下标顺序 i j。如果我先按值排序那么值的大小关系就被排序天然满足了——排序后靠前的元素值一定小于等于靠后的元素值。剩下要解决的就是下标顺序。把每个元素连同原下标一起放进一个列表按值升序排序。然后从左到右遍历这个排序后的列表维护一个“已经看过的最小原下标” min_idx。为什么要维护最小下标因为对于当前遍历到的元素它作为候选右端点想要形成尽可能宽的坡就应该找“排序序列里在它之前出现的、原下标尽量小”的元素当左端点。排序序列靠前说明值小满足值的约束原下标小说明位置靠左满足 i j 且宽度最大。于是i - min_idx就是当前元素作为右端点能提供的最大宽度。代码def max_width_ramp_sort(nums): n len(nums) arr sorted((value, idx) for idx, value in enumerate(nums)) min_idx n ans 0 for _, idx in arr: ans max(ans, idx - min_idx) min_idx min(min_idx, idx) return ans初看这段代码可能会有一个疑问idx - min_idx如果是个负数怎么办没关系因为 ans 初始化是 0负数取 max 会被自动忽略。min_idx初始化为 n 而不是 0就是为了避免首元素被误判成坡第一个元素遍历时idx - n是负数不会污染答案。还是拿[6, 0, 8, 2, 1, 5]验证。排序后得到(0,1) (1,4) (2,3) (5,5) (6,0) (8,2)遍历 (0,1)idx-min_idx 1-6 -5ans0min_idx1遍历 (1,4)4-1 3ans3min_idx1遍历 (2,3)3-1 2ans 保持 3min_idx1遍历 (5,5)5-1 4ans4min_idx1遍历 (6,0)0-1 -1min_idx0遍历 (8,2)2-0 2ans 保持 4。最终结果 4正确。这个解法的时间复杂度是 O(n log n)主要花在排序上空间 O(n)。它的思路比单调栈更“粗暴直接”但胜在容易理解和记忆我在笔试时间紧张的时候经常会先写这个再考虑是否有 O(n) 解法。4.2 二分答案 前缀最小值/后缀最大值判定排序法提供了另一种角度但复杂度是 O(n log n)。还有一个 O(n log n) 的解法思路也值得掌握那就是二分答案。既然题目要求最大宽度而宽度具有单调性——如果宽度 w 可行那么宽度 w-1 一定也可行把坡的右端点往前挪一格就能得到更小的宽度。所以可以二分宽度每次判断“是否存在宽度至少为 w 的坡”。判断函数怎么设计假设要判断是否存在宽度 w 的坡也就是要找到一对下标 i、j满足 j - i w 且 A[i] A[j]。这里可以用前缀最小值和后缀最大值来做定义left_min[i]表示从 0 到 i 的范围内数组的最小值right_max[i]表示从 i 到 n-1 的范围内数组的最大值。对于当前判断的宽度 w遍历 i 从 0 到 n-1-w如果left_min[i] right_max[iw]说明存在一个取值较小的位置 pp i和一个取值较大的位置 qq iw而且 p 一定在 q 的左边p 和 q 之间的下标差至少为 w所以宽度至少为 w 的坡一定存在。代码def max_width_ramp_binary(nums): n len(nums) left_min [0] * n right_max [0] * n cur_min nums[0] for i in range(n): cur_min min(cur_min, nums[i]) left_min[i] cur_min cur_max nums[-1] for i in range(n - 1, -1, -1): cur_max max(cur_max, nums[i]) right_max[i] cur_max def can_ramp(width): for i in range(n - width): if left_min[i] right_max[i width]: return True return False lo, hi 0, n - 1 while lo hi: mid (lo hi 1) // 2 if can_ramp(mid): lo mid else: hi mid - 1 return lo这个解法的巧妙之处在于它把“是否存在一对距离至少为 w 的满足条件的下标”变成一个比较前缀最小值和后缀最大值的问题不需要枚举具体下标对。每次判断是 O(n)二分是 O(log n)所以总复杂度 O(n log n)。它的缺点也很明显代码比单调栈版本长很多常数也更大。不过如果你正在准备算法设计与分析的期末考试老师很有可能会喜欢这种“二分答案 可行性判定”的套路因为它考察的是你能不能把最大值问题转换成一系列判定问题。4.3 三种解法对比什么时候该用哪种我把三种解法的核心特点整理成了一张表方便你对照记忆解法时间复杂度空间复杂度核心思想适合场景暴力枚举O(n^2)O(1)枚举所有下标对理解题意、数据量极小单调栈 反向扫描O(n)O(n)压缩候选左端点反向确定右端点面试最优解、追求极致性能排序下标法O(n log n)O(n)用排序满足值约束遍历维护最小下标笔试快速实现、思路直观二分答案 前后缀最值O(n log n)O(n)宽度二分 可行性判定算法设计课、练习二分思想如果只是做题通过我会优先选单调栈版本因为它复杂度最优。但如果你在真实笔试环境里由于状态紧张单调栈的弹出的正确性容易想不清楚那排序下标法其实是一个更稳妥的替代方案不容易写错也能在 O(n log n) 时间内解决大多数序列长度在 10^5 左右的题目。提示刷题时别只看“哪种最优”也要培养“哪种最不容易写错”的判断力。能稳定 AC 的解法才是好解法。5. 边界条件、调试经验和面试延伸5.1 四类极端输入直接验证实现任何算法题写完第一版都要在脑内跑几个极端用例最大宽度坡也不例外。我总结了四种最容易暴露 bug 的输入第一种是单调递减数组比如[5, 4, 3, 2, 1]。这种情况任意 i j 都有 A[i] A[j]不存在任何坡答案应该是 0。单调栈版本构建出来的候选栈会包含所有下标反向扫描时发现没有 j 能满足nums[stack[-1]] nums[j]ans 保持 0。排序法里每个idx - min_idx都是负数也被 0 忽略。四种实现都能正确返回 0。第二种是单调递增数组比如[1, 2, 3, 4, 5]。最优坡显然是从下标 0 到下标 4宽度 4。单调栈版本里因为 nums 一直递增构建栈时只有下标 0 入栈反向扫描到 j4 时直接更新 ans4正确。第三种是全部相等的数组比如[2, 2, 2, 2]。因为 A[i] A[j] 的等号是成立的所以答案应该是 3。这里要特别注意构建栈时用的是严格递减条件nums[i] nums[stack[-1]]相等时不入栈所以保留的是最靠左的那个下标 0反向扫描 j3 时得到宽度 3。如果你把条件写成栈里会放入所有相等的下标虽然结果可能也不变但候选集合就膨胀了失去了压缩的意义。第四种是只有一个元素或者空数组。LeetCode 的约束一般保证至少有一个元素但作为工具函数最好一开始就写if len(nums) 2: return 0。单元素不存在合法的坡直接返回 0 合情合理。5.2 笔试实战里容易被忽略的细节我在调试这道题时发现了一些容易踩的细节这里统一列一下都是真实经历过的第一个是关于“等于”的处理。左端点入栈条件是严格小于反向扫描更新条件是小于等于。这两个条件一个紧一个松如果搞反了要么答案偏小要么候选集合失效。我的记忆方法是构建左端点时遇到相等的值保留靠右的那个因为更右、宽度更大所以跳过匹配右端点时只要栈顶值小于等于当前右端点值就能形成坡等号必须包含。第二个是排序下标法的min_idx初始值。如果你把 min_idx 初始化为 0第一个元素遍历时idx - 0可能得到一个很大的正数而这个“坡”根本不存在因为第一个元素还没形成任何“之前元素”。所以要么初始化为 n要么用float(inf)保证第一次不产生有效答案。第三个是二分答案法的边界。hi n - 1因为最大宽度不可能超过 n-1。mid (lo hi 1) // 2这种上取整写法是为了避免 lo 和 hi 相差 1 时死循环这是我被坑过一次后才记住的细节。第四个是 Python 性能优化。如果你的解法要过很严格的时间限制尽量少在循环里调用函数比如把len(nums)存成局部变量把ans max(ans, ...)换成 if 比较。我在本地测试时单调栈版本用max函数和用 if 比较大概有 10% 左右的差异某些极限数据下这个差异可能决定是否超时。5.3 单调栈思想的迁移这题背后的算法思维“最大宽度坡”不只是 LeetCode 上的一道题它背后是一整套单调栈思维模式。理解了这个后续刷每日温度、接雨水、柱状图中最大的矩形时都会轻松很多。单调栈的核心价值在于“维护一个按某种顺序排列的候选集合把看似需要两两比较的 O(n^2) 枚举压缩成 O(n) 的扫描”。在最大宽度坡里候选左端点按值严格递减排列在每日温度里候选元素按温度严格递减排列等待右侧第一个更高温度的出现在接雨水里栈用来维护左右边界找到能存水的凹槽结构。本质上都是同一个套路什么时候入栈、什么时候出栈、出栈时能确定什么信息。我自己的经验是学单调栈类题目不能光看题解一定要找一个数组手动模拟一遍入栈、出栈的全过程模拟两三个用例之后脑子里就会形成“栈顶是什么、什么时候该弹出、弹出的那一刻意味着什么”的直觉。手动模拟比看一百遍代码都管用。回过头再看“最大宽度坡”这道题从暴力的 O(n^2) 到单调栈的 O(n)表面上是数据结构的选择实际上是你能不能发现“更靠右且值更小”的候选替代关系。我第二次刷这道题时已经不需要背诵代码只需要在草稿纸上画出那根递减的候选下标链所有代码就顺着这个结构自然流露出来了。这种“先画结构、再写代码”的习惯是我个人在处理算法题时最受用的经验也分享给你。