一、题目描述额

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 

示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

提示：

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

二、题目分析

这道题也是带着困难标签的普通题😶，看图就可以看出来，题目意思大概就是让我们遍历这个图获得空白方块的数量，这个空白方块取决于两边的实体方块的高度，所以自然想到用2个指针分别记录左右的高度，然后在向中间靠拢的过程中遍历空白方块，统计数量。👀

初步思路形成，接下来进行更细致的思考，左右指针从两端向中间移动，想要正确计算储水量需要知道本端的最高点高度，以及确保对方有一个不低于本端最高点的柱子。 左右两端轮流占领目前遍历到的最高点，当一方占据着全局最高点时。另一方前进，直到遇到了一个比全局最高点更高的点，换另一方前进，循环往复直到 left, right 碰面。可移动的一方每步更新自己这侧的最高点，由于另一方此时占据着全局最高点，所以可以保证另一方有一个不低于本方最高点的柱子，也就确保了当前对储水量的计算是正确的。

三、代码实现

1. 初始化：
   • 使用两个指针 left 和 right，分别指向数组的开头和结尾。
   • 使用两个变量 leftMax 和 rightMax，分别记录从左到右和从右到左遍历时的最高柱子高度。
   • 使用 sumWater 记录总的雨水量。
2. 双指针遍历：
   • 当 left < right 时，进行以下操作：
     • 更新 leftMax 和 rightMax：
       • leftMax = Math.max(leftMax, height[left])：更新左侧最高柱子。
       • rightMax = Math.max(rightMax, height[right])：更新右侧最高柱子。
     • 比较 leftMax 和 rightMax：
       • 如果 leftMax < rightMax，说明左侧的柱子限制了雨水的最高高度，因此可以计算 left 位置的雨水量，并移动左指针。
       • 否则，说明右侧的柱子限制了雨水的最高高度，因此可以计算 right 位置的雨水量，并移动右指针。
3. 计算雨水量：
   • 如果 leftMax < rightMax，则 sumWater += leftMax - height[left]，并移动左指针 left++。
   • 否则，sumWater += rightMax - height[right]，并移动右指针 right--。
4. 返回结果：
   • 遍历结束后，sumWater 就是能接住的总雨水量。

class Solution {
    public int trap(int[] height) {
        int n = height.length;
	        int leftMax = 0, rightMax = 0;
	        int left = 0, right = n - 1;
	        int sumWater = 0;
	        while(left < right) {
	        	leftMax = Math.max(leftMax, height[left]);
	        	rightMax = Math.max(rightMax, height[right]);
	        	
	        	if(leftMax < rightMax) {
	        		sumWater += leftMax - height[left];
	        		left++;
	        	} else {
	        		sumWater += rightMax - height[right];
	        		right--;
	        	}
	        }
	    	return sumWater;
    }
}

提交结果

四、总结

这道困难题难度和普通题差不多，最近感觉刷题刷出感觉来了，虽然一天就写这么几道题目，但是在一天工作后能有精力写我觉得就已经很可贵了，是不是该上点有难度的题目了，竟然开始有点小膨胀😎，越来越不把题目放在眼里了，以前的面对题目的恐惧感和毛躁感已经近乎没有了，这就是刷题的感觉吗！快哉！快哉！😊