- 正确答案：接雨水问题要求计算给定非负整数数组（表示地形高度）中，能接住多少单位的雨水。核心解法有四种：暴力法（O(n²)）、动态规划（O(n)空间）、双指针优化（O(1)空间）、单调栈（O(n)时间，可记录左右边界）。最优实用解是双指针法，其正确性基于木桶原理——当前位置能接的水量由左右两侧最高墙中的较小者决定，减去当前高度。 - 解答思路： 1. 暴力法：对每个位置i，分别向左找最大值left_max，向右找最大值right_max，则i处可接水量为min(left_max, right_max) - height[i]（若结果为负则取0）。时间O(n²)，空间O(1)。 2. 动态规划：预处理两个数组left_max[i]表示[0..i]最大高度，right_max[i]表示[i..n-1]最大高度；然后遍历求和。时间O(n)，空间O(n)。 3. 双指针（推荐）：设left=0, right=n-1，维护left_max和right_max。比较height[left]与height[right]： - 若height[left] < height[right]，说明left处的瓶颈必在左侧（因右侧有更高墙），故left处水量仅取决于left_max；更新left_max = max(left_max, height[left])，累加left_max - height[left]，left++。 - 否则处理right侧。该逻辑成立的关键在于：当height[left] < height[right]时，left位置的right_max一定 ≥ height[right] > height[left]，因此min(left_max, right_max) = left_max 当且仅当 left_max ≤ right_max；但即使left_max > right_max，实际瓶颈仍是right_max——然而此时我们不处理left，而是移动right，保证始终用“确定的较小侧”来安全计算。本质是利用“当前较矮侧的水量上限由其同侧最大值决定”这一事实，避免不确定的跨侧依赖。 4. 单调栈：维护一个递减栈，存储下标。遇到height[i] > height[stack.top()]时，弹出栈顶作为凹槽底部bottom，新栈顶为左边界，i为右边界，宽度 = i - stack.top() - 1，高度 = min(height[stack.top()], height[i]) - height[bottom]，累加面积。时间O(n)，每个元素最多入栈出栈一次；空间O(n)。 - 深度知识讲解：本题考察对“局部极小值区间”的建模能力，本质是二维几何中的“封闭洼地”面积计算。关键底层概念包括：（1）木桶原理的算法化表达：任意位置i的蓄水能力受限于其左侧最高墙和右侧最高墙的较小值，这是由流体力学中水往低处流、表面等势的物理约束映射而来；（2）空间换时间的思想演进：从暴力O(n²)到DP O(n)空间，再到双指针O(1)空间，体现算法设计中对冗余信息的识别与消除——DP中left_max[i]与right_max[i]存在大量重复计算，而双指针通过维护“已知可靠边界”实现增量更新；（3）单调栈的几何意义：栈中元素构成“阶梯式下降轮廓”，每次新高点出现即形成以栈中次顶为左壁、当前为右壁、栈顶为底的矩形槽，这是处理“下一个更大元素”类问题的通用范式，底层依赖栈的LIFO特性维持最近历史状态；（4）双指针的数学证明基础：令L=0,R=n-1，left_max = max(height[0..L]), right_max = max(height[R..n-1])。若height[L] < height[R]，则对于位置L，其真实right_max_real ≥ height[R] > height[L]，因此min(left_max, right_max_real) = left_max 当且仅当 left_max ≤ right_max_real；但即使left_max > right_max_real，实际min值是right_max_real，而我们此时并不知道它——然而注意：由于height[L] < height[R]，我们移动的是L，这意味着right_max_real尚未被完全探索，但关键洞察是：此时L位置的蓄水量上限不可能超过left_max - height[L]，且该值一定是安全的下界？不，这不对——正确证明应基于不变式：在每一步，我们保证min(left_max, right_max) 是位置L或R处的真实瓶颈的上界，且当移动指针时，被移动侧的瓶颈已被其同侧最大值完全覆盖。标准证明如下：假设height[L] < height[R]，则无论right_max_real是多少，L处的蓄水量 = min(left_max, right_max_real) - height[L] ≤ left_max - height[L]；但更重要的是，由于height[L] < height[R]，right_max_real ≥ height[R] > height[L]，所以left_max 是min(left_max, right_max_real) 的候选之一；若left_max ≤ right_max_real，则min=left_max，计算正确；若left_max > right_max_real，则min=right_max_real，但我们此时无法计算——然而，这种情况下，right_max_real 必然在R左侧某处，而我们尚未访问到，所以应当先处理R侧？矛盾。正解是：双指针的正确性依赖于“移动较矮侧指针时，该侧的max值即为全局瓶颈的充分代理”。严谨表述为：在任意时刻，若height[L] < height[R]，则位置L的蓄水量只取决于left_max，因为right_max_real ≥ height[R] > height[L]，所以left_max ≤ right_max_real ⇒ min = left_max；反之若left_max > right_max_real，则说明right_max_real < left_max，但height[R] ≤ right_max_real < left_max，又height[L] < height[R]，故height[L] < left_max，这与left_max定义（[0..L]最大值）矛盾（因为height[L] < left_max，说明left_max来自L左侧，合理），但此时height[L] < height[R] ≤ right_max_real < left_max，那么min(left_max, right_max_real)=right_max_real，而我们却用left_max计算，会高估。——此质疑揭示常见误解。真相是：双指针法中，我们**不直接使用left_max作为min值**，而是用“当前已知的left_max和right_max中较小的那个”来代表瓶颈。标准双指针实现如下： left, right = 0, len(height)-1 left_max = right_max = 0 water = 0 while left < right: if height[left] < height[right]: if height[left] >= left_max: left_max = height[left] else: water += left_max - height[left] left += 1 else: if height[right] >= right_max: right_max = height[right] else: water += right_max - height[right] right -= 1 关键点：只有当当前高度小于对应侧max时才累加，且更新max仅发生在当前高度≥max时。此时，若height[left] < height[right]，我们关心left位置能否储水，其条件是left_max > height[left]；而left_max是[0..left]最大值，height[right]是右侧某点，但right_max尚未完全确定。然而，由于height[left] < height[right]，且right_max至少为height[right]，所以right_max > height[left]；但left_max可能很小。真正保证的是：当我们用left_max更新water时，left_max是可信的（来自左侧已遍历部分），而右侧存在至少height[right] > height[left]的墙，因此只要left_max > height[left]，就一定能储水left_max - height[left]，因为右侧有比height[left]更高的墙（height[right]），所以水不会从右漏出；左侧有left_max的墙，所以水不会从左漏出。因此，left_max - height[left] 就是当前位置的实际储水量。同理，当height[left] >= height[right]时，用right_max计算。因此，该算法的物理意义是：每次选择较矮的边界墙，用其同侧已知最高墙作为储水顶盖，另一侧已有更高墙保证不溢出。 - 伪代码（双指针法，清晰版）： function trap(height): if not height or len(height) < 3: return 0 left, right = 0, len(height) - 1 left_max, right_max = 0, 0 water = 0 while left < right: if height[left] < height[right]: if height[left] >= left_max: left_max = height[left] else: water += left_max - height[left] left += 1 else: if height[right] >= right_max: right_max = height[right] else: water += right_max - height[right] right -= 1 return water - 扩展知识：（1）变种问题：接雨水II（二维矩阵）需用最小堆+BFS，将边界入堆，每次弹出最小高度，其邻居若更低则可蓄水，差值累加，并将邻居以max(neighbor, popped_height)入堆；（2）与“最大矩形面积”问题对比：后者用单调栈求每个柱子作为高时的最大宽度，而接雨水是求每个位置作为底时的最大水深；（3）工程应用：地形分析、芯片散热沟槽设计、图像处理中的阴影校正；（4）测试用例设计要点：空数组、单/双元素、全相同高度、严格递增/递减、峰谷交替（如[0,1,0,2,1,0,1,3,2,1,2,1]）——该例答案为6。 - 代码示例（Python，含注释）： def trap(height): n = len(height) if n < 3: return 0 left, right = 0, n - 1 left_max, right_max = height[0], height[n-1] water = 0 while left < right: # 移动较矮的一侧，因为它的蓄水能力由其同侧max决定，且另一侧已有更高墙兜底 if height[left] < height[right]: if height[left] > left_max: left_max = height[left] else: water += left_max - height[left] left += 1 else: if height[right] > right_max: right_max = height[right] else: water += right_max - height[right] right -= 1 return water

日常实习-字节多模态一面 30min

全站热榜

创作者周榜