LeetCode_Array_42. Trapping Rain Water 接雨水【雙指針】【Java】【困難】

目錄

​​一，題目描述​​

​​英文描述​​

​​中文描述​​

​​示例與說明​​

​​二，解題思路​​

​​三，AC代碼​​

​​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​

​ 的柱子的高度圖，計算按此排列的柱子，下雨之後能接多少雨水。

示例與說明

連結：​​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] > maxLeft，則更新maxLeft的值;
• 否則說明對于目前位置left，左右均有高度大于height[left]的柱子，隻需要選擇其中較矮的一個，減去height[left]即可。