LeetCode|LeetCode_Array_42. Trapping Rain Water 接雨水【双指针】【Java】【困难】接雨水|双指针|困难|力扣|jav

目录
一，题目描述
英文描述
中文描述
示例与说明
二，解题思路
三，AC代码
Java
【LeetCode|LeetCode_Array_42. Trapping Rain Water 接雨水【双指针】【Java】【困难】】四，解题过程
第一搏
第二搏

一，题目描述英文描述

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

中文描述

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

示例与说明

LeetCode|LeetCode_Array_42. Trapping Rain Water 接雨水【双指针】【Java】【困难】

文章图片

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/trapping-rain-water
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二，解题思路核心思路：对于每一个位置i，只需要知道该位置左右两侧最高的柱子高度，即可求出该位置能存储的水量。
一种非常巧妙的方法是：用left和right限定左右区间，maxLeft、maxRight记录遍历过程中遇到的最大值。
当height[left] <= height[right]时：

若height[left] > maxLeft，则更新maxLeft的值;
否则说明对于当前位置left，左右均有高度大于height[left]的柱子，只需要选择其中较矮的一个，减去height[left]即可。

但注意！由于是左边界在向中间移动，所以左侧柱子的高度必定小于height[right]的高度！！！
而此时maxRight不一定大于height[right]（因为还没更新），所以较矮的一定是maxLeft，也就是说ans += (maxLeft - height[left])，而不是ans += (min(maxLeft, maxRight) - height[left])

三，AC代码 Java

class Solution { public int trap(int[] height) { if (height.length <= 2) return 0; int left = 0, right = height.length - 1; // 标记左右边界 int maxLeft = 0, maxRight = 0; // 记录目前遇到的最大高度，初始化为0!!! int ans = 0; while (left < right) { if (height[left] <= height[right]) { if (height[left] > maxLeft) maxLeft = height[left]; else ans += (maxLeft - height[left]); // !!!到这里表示一定有右边界大于maxLeft，所以只需要取maxLeft即可，而不是取min(maxLeft, maxRight)，因为maxRight可能还没来得及更新 left++; } else { if (height[right] > maxRight) maxRight = height[right]; else ans += (maxRight - height[right]); // !!!同上 right--; } } return ans; } }

四，解题过程第一搏数组maxLeft和maxRight分别记录从左到右、从右到左遍历过程中当前位置遇到的最大值，其中maxLeft[i]表示，从左向右遍历到 i 时，遇到的最大值，maxRight同理。
再次遍历数组height，对每一个位置 i 计算ans += (Math.min(maxLeft[i], maxRight[i]) - height[i]); 即对每一个位置 i 计算该位置可以存储的最大水量。

class Solution { public int trap(int[] height) { if (height.length <= 2) return 0; int[] maxLeft = new int[height.length]; // 存储从左到右中最高的柱子高度 int[] maxRight = new int[height.length]; // 存储从右到左中最高的柱子高度 maxLeft[0] = height[0]; maxRight[height.length - 1] = height[height.length - 1]; for (int i = 1; i < height.length; i++) { maxLeft[i] = Math.max(maxLeft[i - 1], height[i]); } for (int i = height.length - 2; i >= 0; i--) { maxRight[i] = Math.max(maxRight[i + 1], height[i]); } int ans = 0; for (int i = 1; i < height.length - 1; i++) { ans += (Math.min(maxLeft[i], maxRight[i]) - height[i]); } return ans; } }

文章图片

额外开两个数组，空间O(n)。
第二搏其实在遍历求解过程中，只需要知道当前位置左侧最高的柱子和右侧最高的柱子高度即可。
一种非常巧妙的方法是：用left和right限定左右区间，maxLeft、maxRight记录遍历过程中遇到的最大值。
当height[left] <= height[right]时：