【Hot 100 刷题计划】 LeetCode 42. 接雨水 | C++ 动态规划与双指针题解

LeetCode 42. 接雨水 | C 动态规划与双指针双解法题解 题目描述题目级别困难 (Hard)给定n个非负整数表示每个宽度为1的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。示例 1:输入height [0,1,0,2,1,0,1,3,2,1,2,1]输出6 解题思路核心物理定律 (木桶效应)接雨水问题的核心在于**“化整为零”。我们不要从整体去考虑能接多少水而是把目光聚焦在每一根单独的柱子**上。问下标为i的这根柱子它的正上方到底能积攒多少水答根据“木桶效应”这取决于它左边所有柱子中的最高点以及右边所有柱子中的最高点。具体公式为第 i 列的水量 min(左边最高, 右边最高) - 当前柱子的高度(如果算出来是负数说明当前柱子比两边都高存不了水取 0 即可) 解法一前后缀分解 / 动态规划 (空间 O(N))既然每一列都需要知道“左边最高”和“右边最高”我们可以提前把它们算出来存进数组里。从左往右遍历一次生成left_max数组记录每个位置及其左边的最高高度。从右往左遍历一次生成right_max数组记录每个位置及其右边的最高高度。最后再遍历一次原数组利用上面的公式计算水量并累加。 C 代码实现 (标准规范版)classSolution{public:inttrap(vectorintheight){intnheight.size();if(n0)return0;// 规范做法使用 vector 代替变长数组vectorintleft_max(n);vectorintright_max(n);// 1. 预处理左侧最大值数组left_max[0]height[0];for(inti1;in;i){left_max[i]max(left_max[i-1],height[i]);}// 2. 预处理右侧最大值数组right_max[n-1]height[n-1];for(intin-2;i0;i--){right_max[i]max(right_max[i1],height[i]);}// 3. 计算总积水量intres0;for(inti0;in;i){resmin(left_max[i],right_max[i])-height[i];}returnres;}}; 解法二双指针 (时间 O(N)空间 O(1) 面试终极解)解法一虽然快但占用了额外的数组空间。能不能用O(1)O(1)O(1)的空间解决答案是双指针。我们在数组两端分别放置指针 left 和 right同时用两个变量 l_max 和 r_max 来记录左右两边见过的最高高度。既然决定水量的木板是短板那么如果lmaxrmaxl_{max} r_{max}lmax​rmax​说明左边这块板子更短。虽然我们不知道 right 指针以右还有没有更高的板子但水桶的高度已经被左边的lmaxl_{max}lmax​锁死了。此时我们可以放心地结算 left 指针所在列的水量并将 left 向右移。反之如果lmaxrmaxl_{max} r_{max}lmax​rmax​说明右边是短板高度被rmaxr_{max}rmax​锁死。我们结算 right 指针所在列的水量并将 right 向左移。 进阶 C 代码实现classSolution{public:inttrap(vectorintheight){intnheight.size();if(n0)return0;intleft0,rightn-1;intl_max0,r_max0;intres0;while(leftright){// 更新左右两端的历史最高点l_maxmax(l_max,height[left]);r_maxmax(r_max,height[right]);// 谁是短板谁就决定了当前列的水量并向中间移动if(l_maxr_max){// 左侧是短板结算 left 处的水量resl_max-height[left];left;}else{// 右侧是短板结算 right 处的水量resr_max-height[right];right--;}}returnres;}};