【力扣热题100】双指针—— 接雨水

题目

给定 n 个非负整数表示每个宽度为 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 个单位的雨水（蓝色部分表示雨水）。

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

链接：[https://leetcode.cn/problems/3sum/description/?envType=study-plan-v2&envId=top-100-liked)

思路

思路一（超时）

暴力：对于每个位置，找到左右最高的高度，计算当前位置的雨水，加和。O(N²)会超时

思路二

在暴力的基础上进行优化，先遍历一遍提前知道每个位置左右最高高度，然后对于每个位置，计算当前位置的雨水，加和。O(N)

class Solution {public int trap(int[] height) {int sum = 0;int[] max_left = new int[height.length];int[] max_right = new int[height.length];// 提前知道每个位置左右最高高度for (int i = 1; i < height.length - 1; i++) {max_left[i] = Math.max(max_left[i - 1], height[i - 1]);}for (int i = height.length - 2; i >= 0; i--) {max_right[i] = Math.max(max_right[i + 1], height[i + 1]);}// 计算当前位置盛水量for (int i = 1; i < height.length - 1; i++) {int min = Math.min(max_left[i], max_right[i]);if (min > height[i]) {sum = sum + (min - height[i]);}}return sum;}
}

思路三

在思路二的基础上继续优化，在遍历的过程中就知道左右最高高度，从而节省空间复杂度。
一个位置能盛放的雨水量，是由当前位置和**左右最高高度中较小的高度决定的。**因此，双指针从头尾进行遍历，每次移动较矮的。在移动的过程中记录水量。

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

思路四（超时）

首先找到最高的高度max，在实际下雨的过程中，首先高度为1的地方都是水，然后是高度为2的地方都是水，依次到高度为max的地方。
那么对于当前的高度i，找到最左和最右高度为i的位置left和right。那么在这中间的这段区域都可能有水，比较每个位置的高度和i的关系即可，满足则总水量+1。

class Solution {public int trap(int[] height) {int max = 0;for (int i = 0; i < height.length; i++) {max = Math.max(height[i], max);}int result = 0;for (int i = 1; i <= max; i++) {int left = 0;int right = height.length -1;while (left < right) {if (height[left] < i) {left++;} else if (height[right] < i) {right--;} else {for (int j = left+1; j < right; j++) {if (height[j] < i) {result++;}}break;}}}return result;}
}