タイトル

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
For example,  Given  [0,1,0,2,1,0,1,3,2,1,2,1] , return  6 .
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. 

class Solution {
public:
    int trap(int A[], int n) {
    }
};

 
X軸上の各領域の幅が1の海抜図を表すn個の非負の整数を与え,この海抜図が最大でどれだけの(面積)雨水を受け取ることができるかを計算した.
Paste_Image.png
例えば上図に示すように、海抜はそれぞれ[0,1,0,2,1,0,1,3,2,1]であり、6を返す.

ぶんせき

3つの方法で解決できる

方法1:

まず左から一度遍歴して、各点の左の最高点数値(一番左の点から、今の点までのすべての点の中の最高高さ)を求めます.もう一度右側を遍歴して、各点の右側の最高点数値(一番右の点から、現在の点までのすべての点の中での最高高さ)を求めます.水をキャッチできるようにするには、その点の左右の2つの最高点数値(上から2回遍歴して求めた)のうち、最小の数値(つまり高さ)は中間より大きいはずです.受け止められる水の面積はこの2つの数字の差です.

public class Solution {
    /**
     * @param heights: an array of integers
     * @return: a integer
     */
    public int trapRainWater(int[] A) {
        if(A == null || A.length < 3)
            return 0;

        int localMax = A[0];
        int[] left = new int[A.length];
        int[] right = new int[A.length];

        for(int i=0;iif(A[i] <= localMax)
                left[i] = localMax;
            else {
                localMax = A[i];
                left[i] = localMax;
            }
        }

        localMax = A[A.length-1];
        for(int i=A.length-1;i>-1;i--) {
            if(A[i] <= localMax)
                right[i] = localMax;
            else {
                localMax = A[i];
                right[i] = localMax;
            }
        }

        int area = 0;
        for(int i=0;ileft[i], right[i]) - A[i];
        }

        return area;
    }
}

方法2

まず、一番高い点を探して、左右からそれぞれ一番高い点に進みます.
注:ここの最高点は最高の仕切り板に相当します.最高の仕切り板の左側にある板にとって、左側に隣接する板の高さがそれより高い限り、水を貯めることができます(この板の右側に隣接する板の高さを考慮する必要はありません.最高の仕切り板は水が閉じ込められることを保証しているからです).
一方、最高仕切板の右側に位置する板では、右側に隣接する板の高さがそれより高い限り、水を貯留することができる(この板の左側に隣接する板の高さを考慮する必要はない.最高仕切板は水が閉じ込められることを保証しているからだ).

public class Solution {
    /**
     * @param heights: an array of integers
     * @return: a integer
     */
    public int trapRainWater(int[] heights) {
        if(heights.length <= 2) return 0;
        int max = -1, maxInd = 0;
        int i = 0;
        for(; i < heights.length; ++i){
            if(heights[i] > max){
                max = heights[i];
                maxInd = i;
            }
        }
        int area = 0, root = heights[0];
        for(i = 0; i < maxInd; ++i){
            if(root < heights[i]) root = heights[i];
            else area += (root - heights[i]);
        }
        for(i = heights.length-1, root = heights[heights.length-1]; i > maxInd; --i){
            if(root < heights[i]) root = heights[i];
            else area += (root - heights[i]);
        }
        return area;
    }
}

方法3

左右の2つの針が、1つ1つと1つと巡り始め、まず自分の側の局部の最高点を見つけ、最高点より小さくさえあれば水を入れることができます.
これは方法1と似ています.

public class Solution {
    /**
     * @param heights: an array of integers
     * @return: a integer
     */
    public int trapRainWater(int[] A) {
        if(A == null || A.length < 3)
            return 0;

        //             
        int left = 0;
        int right = A.length-1;
        //                 
        int leftMax = 0;
        int rightMax = 0;

        int area = 0;

        while(left <= right) {
            leftMax = Math.max(leftMax, A[left]);
            rightMax = Math.max(rightMax, A[right]);

            //        
            if(leftMax <= rightMax) {
                if(leftMax > A[left])
                    area += leftMax - A[left];
                left++;
            }
            else {
                if(rightMax > A[right])
                    area += rightMax - A[right];
                right--;
            }
        }

        return area;
    }
}