循环逻辑一步步说每次先更新左右两边的最高墙看看当前柱子会不会刷新left_max/right_max判断如果左边最高墙 右边最高墙✅ 说明对于left这个位置它能存水的上限就是left_max。因为右边已经有一堵更高的墙兜底了不用担心右边不够高水不会流走。能存水 left_max - height[left]加到结果左指针右移。否则right_max left_max✅ 说明对于right这个位置存水上限是right_max。左边有更高的墙兜底水不会往左跑。能存水 right_max - height[right]加到结果右指针左移。直到两个指针碰面全部位置算完返回总雨水。pythonclassSolution(object):deftrap(self,height): :type height: List[int] :rtype: int left,right0,len(height)-1left_maxright_max0res0whileleftright:left_maxmax(left_max,height[left])right_maxmax(right_max,height[right])ifleft_maxright_max:resleft_max-height[left]left1else:resright_max-height[right]right-1returnresc时间和空间复杂度均为O(N)但是思路好理解classSolution{public:inttrap(vectorintheight){// 遍历到i位置就只关心该位置能接多少雨水// 通过两个数组来维护0-i的最大高度和i到n-1的最大高度// 再根据木桶效应得知i位置能接的雨水只与这两个最大值中的较小值有关intnheight.size();vectorintleft_max(n,height[0]);vectorintright_max(n,height[n-1]);intres0;for(inti1;in;i){left_max[i]max(height[i],left_max[i-1]);}for(intin-2;i0;i--){right_max[i]max(height[i],right_max[i1]);}for(inti0;in;i){resmin(left_max[i],right_max[i])-height[i];}returnres;}};时间复杂度仍为O(N)优化空间复杂度为O(1)思路稍微有些绕classSolution{public:inttrap(vectorintheight){// 遍历到某个位置就只关心该位置能接多少雨水// 通过两个变量max_left和max_right可以得知左指针left和右指针right的height[0:left]和height[right:-1]的各自最大值// 再根据木桶效应得知某个位置能接的雨水只与这两个最大值中的较小值有关intleft0,rightheight.size()-1;intmax_left0,max_right0;intres0;while(leftright){max_leftmax(max_left,height[left]);max_rightmax(max_right,height[right]);if(max_leftmax_right){resmax_left-height[left];left;}else{resmax_right-height[right];right--;}}returnres;}};