关于LeetCode第42题的题解

。2. 核心思路双指针 / 峰值分割法本题采用「峰值分割法」核心思想是先找到全局最高柱再分别从左右两侧向最高柱逼近逐格累加雨水量第一趟遍历找到全局最高柱的下标lo它把数组分成左右两半从左侧向lo遍历维护一个leftMax记录左侧已出现的最高柱当height[i] leftMax时说明当前位置能接到leftMax - height[i]的水从右侧向lo遍历维护一个rightMax记录右侧已出现的最高柱当height[i] rightMax时累加rightMax - height[i]左右两半累加的总和即为总接水量。这样只需三趟线性遍历即可完成计算且不需要额外数组。3. 复杂度分析时间复杂度O(n)共进行三趟线性遍历找最高柱、左半遍历、右半遍历总体仍是线性时间。空间复杂度O(1)只使用了常数个额外变量满足题目「就地计算」的要求。4. 边界条件数组为空或长度为 1height.length 1时无法形成凹槽三趟循环都不会累加水量直接返回 0代码安全。数组单调递增例如[0, 1, 2, 3]最高柱在最右侧左半遍历时leftMax始终不小于当前高度不会累加右半为空结果为 0符合预期。数组单调递减例如[3, 2, 1, 0]最高柱在最左侧左半为空右半遍历时rightMax始终不小于当前高度不会累加结果为 0。经典凹槽例如[0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]最高柱为下标 7 的3左半累加得到 5右半累加得到 1总接水量为 6与题目示例一致。多个相同最高柱取第一个最高柱作为分割点左右两侧仍能正确累加结果不受影响。classSolution{publicinttrap(int[]height){intsum0;intmaxInteger.MIN_VALUE;intlo0;for(inti0;iheight.length;i){if(height[i]max){maxheight[i];loi;}}intleftMax0;for(inti0;ilo;i){if(height[i]leftMax){leftMaxheight[i];}if(height[i]leftMax){sumsum(leftMax-height[i]);}}intrightMax0;for(intiheight.length-1;ilo;i--){if(height[i]rightMax){rightMaxheight[i];}if(height[i]rightMax){sumsum(rightMax-height[i]);}}returnsum;}}