- 正确答案：接雨水问题的经典解法是双指针法（时间O(n)，空间O(1)）或动态规划法（时间O(n)，空间O(n)）。最优实现为双指针法，核心思想是：对于每个位置i，能接的水量 = min(左侧最高柱子高度, 右侧最高柱子高度) - 当前柱子高度，且结果非负。双指针通过维护left_max和right_max两个变量，在左右指针向中间收缩过程中，只在确定某侧边界更小时才移动该侧指针并计算该位置的存水量。 - 解答思路： 1. 观察发现：位置i能否存水，取决于它左边所有柱子的最大值（left_max）和右边所有柱子的最大值（right_max）——即“木桶效应”。只有当height[i] < min(left_max, right_max)时才能存水，水量为差值。 2. 暴力法（对每个i遍历求left_max/right_max）时间复杂度O(n²)，不可取。 3. 动态规划预处理：用两个数组left_max[i]表示[0..i]最大值，right_max[i]表示[i..n-1]最大值，再遍历一次求和。空间O(n)。 4. 双指针优化：利用“若left_max < right_max，则left处的存水量完全由left_max决定（因右侧必有≥right_max ≥ left_max的柱子），此时可安全计算left位置水量并left++；反之处理right”。这样仅需O(1)空间，单次遍历。 - 深度知识讲解：本题本质考察对“单调性”与“边界控制”的理解，是典型的“以空间换时间”到“以逻辑换空间”的优化范例。关键底层原理在于： • 单调性保证：left_max随left右移非递减，right_max随right左移非递减； • 决策依据的数学证明：假设left_max < right_max，那么对位置left，其真实left_bound = left_max，而真实right_bound ≥ right_max（因right_max是[right..end]最大值，当前right在left右侧，故[right..end] ⊆ [left+1..end] ⇒ right_bound ≥ right_max > left_max），因此min(left_bound, right_bound) = left_max —— 即left处水量仅由left_max决定，无需知道精确的right_bound。同理right侧。 • 算法稳定性：双指针不会漏掉任何位置（left和right覆盖所有索引），且每个位置仅访问一次。 • 边界条件：数组长度<3时直接返回0（至少需要三个柱子才可能形成凹陷）。 • 扩展思考：若改为“接最多雨水的连续子区间”（二维变体），则转为单调栈或滑动窗口问题；若支持修改柱高（动态查询），需上线段树或树状数组维护区间最值。 - 代码示例（双指针法，含详细注释）： ``` def 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]: # 此时left_max < height[right] <= true right_max => 左侧边界起决定作用 if height[left] >= left_max: left_max = height[left] else: water += left_max - height[left] left += 1 else: # 此时height[left] >= height[right], 且right_max <= height[left] <= true left_max if height[right] >= right_max: right_max = height[right] else: water += right_max - height[right] right -= 1 return water ``` - 补充：单调栈解法（同样O(n)时间）亦高频出现，用于强调“最近更大元素”模式：栈中存递减下标，遇到height[i] > height[stack[-1]]时，弹出top作为“凹槽底”，stack[-1]为左边界，i为右边界，宽度 = i - stack[-1] - 1，高度 = min(height[stack[-1]], height[i]) - height[top]。此解法凸显栈在“边界配对”类问题中的通用性，但空间复杂度O(n)，且理解门槛略高。

腾讯视觉大模型算法实习二面

全站热榜

创作者周榜