1.这是一道非常经典的力扣困难题考察双指针。题意不难理解一开始想到的思路如下为定义左右指针从头开始遍历数组令左边为木桶短边一直向右寻找比这条短边更长的长边找到后累加木桶容积。完整代码如下1. int trap(int* height, int heightSize) { 2. int l 0, r l 1; 3. int res 0; 4. while (l heightSize - 2){ 5. while (r heightSize height[r] height[l]) r; 6. if (r heightSize || r - l 1){ 7. l; 8. r l 1; 9. continue; 10. } 11. 12. for (int i l 1; i r; i){ 13. res height[l] - height[i]; 14. } 15. l r; 16. r l 1; 17. } 18. 19. return res; 20. }2.代码中还包含了一些简单的剪枝操作剩余元素个数小于3则一定没有容积l heightSize - 2、找到的长边与之前的短边只相差距离1则没有容积r - l 1。3.本地算例通过了但是提交答案出错了报错如下可以看到对于这个数组唯一的木桶短边在右侧而我的代码默认了“右边界一定要比左边界高或等高”所以一定会漏掉这种情况导致输出容积为0说明当前的方法考虑不周全。4.尝试另一种方法先假定左边为木桶的一边然后去寻找凹槽即第一个比该边短的长度之后再去寻找第一个比该凹槽短边长的边为木桶另一边比较木桶两边中的短边为实际边长计算容积。完整代码如下1. int trap(int* height, int heightSize) { 2. if (heightSize 3) return 0; 3. 4. int l 0, r l 1; 5. int res 0; 6. while (l heightSize - 2){ 7. while (r heightSize height[r] height[l]){ 8. l; 9. r; 10. if (l heightSize - 2) return 0; 11. } 12. 13. int tmp height[r]; 14. while (r heightSize height[r] tmp) r; 15. if (r heightSize){ 16. l; 17. r l 1; 18. continue; 19. } 20. 21. int len fmin(height[l], height[r]); 22. for (int i l 1; i r; i){ 23. res len - height[i]; 24. } 25. l r; 26. r l 1; 27. } 28. 29. return res; 30. }5.这次连第二个本地算例都没有通过报错如下对于这个数组如果用我的代码右边找到3时就会停下计算容积但实际上的右边应该为5导致容积计算错误。这是因为我的代码用的是“局部贪心”思想找到一个凹槽就累加到容积中但忽视了“大桶套小桶”的情况导致漏算容积。6.本题的正确做法是从“横向找容器”转变为“纵向找水柱”不再去管局部容器的左右边界反而去关注“第i根柱子上能放多少水”。以下是完整答案1. int trap(int* height, int heightSize) { 2. // 少于3根柱子无法形成积水直接返回0 3. if (heightSize 3) return 0; 4. 5. // l左指针r右指针 6. int l 0, r heightSize - 1; 7. // l_max左侧最高柱子高度r_max右侧最高柱子高度 8. int l_max 0, r_max 0; 9. // 累计雨水总量 10. int res 0; 11. 12. while (l r){ 13. // 更新左右两侧最高高度 14. l_max fmax(l_max, height[l]); 15. r_max fmax(r_max, height[r]); 16. 17. // 左侧柱子更矮积水由左侧最高墙决定 18. if (height[l] height[r]){ 19. res l_max - height[l]; 20. l; 21. } else { 22. // 右侧柱子更矮积水由右侧最高墙决定 23. res r_max - height[r]; 24. r--; 25. } 26. } 27. 28. return res; 29. }该算法时间复杂度为O(n)空间复杂度为O(1)。7.为什么官方题解中说“如果height[l] height[r]则必有l_max r_max”对于height[l] height[r]此时有四种情况①height[l] l_maxheight[r] r_max②height[l] l_maxheight[r] r_max③height[l] l_maxheight[r] r_max④height[l] l_maxheight[r] r_max对于①③两种情况很容易得出证明主要看②和④。这其中涉及到该算法中双指针移动的底层逻辑即“谁小谁移动”。为什么现在height[l]小于l_max了说明l移动了而移动的原因便是在右边出现了一个比l_max更大的元素x这个元素x小于等于r_max所以可得height[l] l_max x r_max也就可以直接证明出l_max r_max且证明过程实际上与height[r]无关。对于“如果height[l] height[r]则必有l_max r_max”的证明也是如此。8.该算法的实际过程类似于我的第一个“横向找短板”的双向版本我的代码只考虑了从左向右这一单边方向而实际上应该使用左右双向将这个数组分成左右两个区间来分别计算容积最后左右指针汇聚到最高的柱子处。比较height[l]和height[r]的大小可以保证永远是矮的那一边来计算容积它的另一边一定是更高的。9.官方还给出了动态规划的解法但我看官方这张图这难道不是小学奥数的“容斥”问题吗先从左向右遍历得到完整面积中的右边再从右向左遍历得到完整面积的左边最后遍历得出完整面积由于每块独立面积都包含最后的容积面积所以两块独立面积相加后再减去完整面积就是容积。完整代码如下1. int trap(int* height, int heightSize) { 2. // 柱子数量小于3无法蓄水直接返回0 3. if (heightSize 3) return 0; 4. 5. // l_max从左往右遍历记录的全局最大高度r_max从右往左遍历记录的全局最大高度 6. int l_max 0, r_max 0; 7. 8. // resl只以左侧最高墙计算每个位置能存的水量总和不考虑右侧墙体限制 9. int resl 0; 10. for (int i 0; i heightSize; i){ 11. l_max fmax(l_max, height[i]); 12. // 当前柱子低于左侧最高墙则可以存水 13. if (height[i] l_max){ 14. resl l_max - height[i]; 15. } 16. } 17. 18. // resr只以右侧最高墙计算每个位置能存的水量总和不考虑左侧墙体限制 19. int resr 0; 20. for (int i heightSize - 1; i 0; i--){ 21. r_max fmax(r_max, height[i]); 22. if (height[i] r_max){ 23. resr r_max - height[i]; 24. } 25. } 26. 27. // 单独用全局左最大高度算出的总水量是每个位置左墙高度减柱子高度 28. int res 0; 29. for (int i 0; i heightSize; i){ 30. res l_max - height[i]; 31. } 32. // 容斥原理真实蓄水量 左单边累加 右单边累加 - 全局高墙单边累加 33. res resl resr - res; 34. 35. return res; 36. }该算法时间复杂度为O(n)空间复杂度为O(1)。10.而官方的解法是在两次单向遍历时分别记录两种方向上水柱的最大值之后用两个最大值中的最小值来减去柱子的高度得出实际上的水柱高度本质上也是在以最大柱子为界限的左右边界上做文章。该题目确实经典值得之后多次回顾。官方题解中还有单调栈的解法后面学到单调栈的时候再回来看看。