- 正确答案：接雨水问题要求计算给定非负整数数组（表示地形高度）中，能接住多少单位的雨水。经典解法有四种：暴力法、动态规划（双数组）、双指针优化、单调栈。最优解为双指针法，时间复杂度O(n)，空间复杂度O(1)；单调栈法可拓展至二维或变种问题（如雨水II），时间O(n)，空间O(n)。 - 解答思路：核心观察是——每个位置i能接的雨水量 = min(左侧最高墙, 右侧最高墙) - height[i]，前提是该值 > 0。暴力法对每个i遍历左右求max，时间O(n²)；动态规划预处理left_max[i]和right_max[i]数组，避免重复计算，空间O(n)；双指针法利用“木桶效应”：维护left=0、right=n-1及left_max、right_max两个变量；当height[left] < height[right]时，left处的瓶颈必由left_max决定（因right_max >= 当前right_max，且右侧存在更高墙），故可立即计算left位置雨水并left++；反之处理right。该逻辑成立的关键在于：若height[left] < height[right]，则left位置的雨水量仅取决于left_max与height[left]，无需知道精确的right_max，只需保证存在一个>=left_max的右边界墙即可。单调栈法则将问题转化为“寻找每个柱子左侧和右侧第一个更高柱子”，用单调递减栈维护候选左边界，遇到更高右边界时弹出栈顶并计算凹槽面积（宽度 × 高度差）。 - 深度知识讲解： 1. **底层原理与数据结构选择**： - 双指针法本质是贪心+分治思想的结合，其正确性依赖于不等式推理：设L_max = max(height[0..left])，R_max = max(height[right..n-1])，当height[left] < height[right]，则必有L_max <= R_max？不一定，但关键结论是：left位置的瓶颈高度 = min(L_max, global_right_max) ≤ L_max，而我们已知global_right_max ≥ height[right] > height[left]，所以只要L_max < height[right]，left处的雨水就由L_max决定；若L_max ≥ height[right]，则说明右侧存在≥L_max的墙，此时left处瓶颈仍为L_max。因此无论哪种情况，left处的雨水量 = max(0, L_max - height[left])，且L_max已知。这是双指针法数学严谨性的核心。 - 单调栈体现“最近更大元素”（Next Greater Element, NGE）模式，是解决区间约束类问题的通用范式。栈中存储下标，保持height[stack[i]]严格递减；当遇到height[i] > height[stack.top()]时，栈顶元素找到左右边界（新i为右，新栈顶为左），形成以栈顶为底、左右为壁的矩形凹槽。此处“凹槽”实际是横向分层计算（按行求和），每层高度为min(height[left], height[right]) - height[top]，宽度为i - stack.top() - 1。该模型可自然推广到二维接雨水（LeetCode 407）——使用优先队列（最小堆）模拟“从外围最低点向内灌水”。 2. **边界与稳定性分析**： - 所有方法均需处理height为空、单元素、全零等corner case。双指针法初始化left_max = height[0], right_max = height[n-1]，避免下标越界。 - 算法稳定性：接雨水本身不涉及元素交换，无稳定性概念；但若扩展为“带索引的动态接雨水”，则需考虑数据结构的更新效率（如线段树/树状数组支持单点修改+区间查询）。 3. **工程权衡**： - 时间敏感场景（如高频实时计算）选双指针； - 需复用中间结果（如多次查询不同区间的积水）则预处理DP数组； - 若需调试每一步积水分布（如可视化），单调栈更直观，因它显式记录每个凹槽的构成。 - 代码示例（双指针法，含详细注释）： ``` def trap(height): if not height or len(height) < 3: return 0 left, right = 0, len(height) - 1 left_max, right_max = height[left], height[right] water = 0 while left < right: if height[left] < height[right]: # 此时left位置的瓶颈只可能由left_max决定 # 因为右侧至少有一个墙>=height[right]>height[left]，足够作为右边界 if height[left] < left_max: water += left_max - height[left] else: left_max = height[left] # 更新left_max left += 1 else: # 同理，right位置瓶颈由right_max决定 if height[right] < right_max: water += right_max - height[right] else: right_max = height[right] right -= 1 return water ``` - 代码示例（单调栈法，标准实现）： ``` def trap(height): if not height: return 0 stack = [] # 存储下标，维持height单调递减 water = 0 for i in range(len(height)): # 当前高度大于栈顶，形成凹槽 while stack and height[i] > height[stack[-1]]: top = stack.pop() if not stack: # 无左边界，无法形成凹槽 break # 宽度 = i - stack[-1] - 1 （stack[-1]是新的左边界下标） # 高度 = min(height[stack[-1]], height[i]) - height[top] width = i - stack[-1] - 1 bounded_height = min(height[stack[-1]], height[i]) - height[top] water += width * bounded_height stack.append(i) return water ```

26秋招京东Java后端一面

全站热榜

创作者周榜