42. Trapping Rain Water

一、题目

　　1、审题

　　2、分析：

　　　　给出一组整数坐标，代表在 x 轴上的单位为1的木块的高度，求得这些木块之间最多可以积多少水。

二、解答

　　1、思路：

　　　　方法一：a、求出最高的木块的高度，记其下标为 index；

　　　　　　　　b、求 index 左方最高木块的下标， secondIndex；并可以求出 secondIndex 与 index 之间的积水；

　　　　　　　　c、令 index = secondIndex，循环求出 index 左方的全部积水， 当 index = 0 时跳出循环；

　　　　　　　　d、同理可求 index 右方积水。

　　

public class Solution {
    public int trap(int[] height) {
        int end = height.length - 1;
        if( end < 2) return 0;
        
        int index = findMaxNumberIndex(height, 0, end);
        
        int result = 0;
        int i = index, j = index;
        
        while(i != 0) {
            
            int secondIndex = findMaxNumberIndex(height, 0, i-1);
            result += countMediumWater(height, secondIndex, i);
            i = secondIndex;
        }
        while (j != end) {
            int secondIndex = findMaxNumberIndex(height, j+1, end);
            result += countMediumWater(height, j, secondIndex);
            j = secondIndex;
        }
        
        System.out.println(result);
        return result;
    }

    private int findMaxNumberIndex(int[] height, int start, int end) {
        int index = start;
        for (int i = start + 1; i <= end; i++) {
            if(height[i] > height[index]) {
                index = i;
            }
        }
        return index;
    }

    private int countMediumWater(int[] height, int start, int end) {
        
        if(start == end - 1) return 0;
        int block = 0;
        for (int i = start+1; i < end; i++) 
            block += height[i];
        int result = Math.min(height[start], height[end]) * (end-start-1) - block; 
        return result;
    }
}

　　方法二、a、 定义两个指针，left 指向 0，向右移动； right 指向数组最后一个元素，向左移动；

　　　　　　b、定义3个变量， leftMax代表 left 向右移动时的木块最高长度，rightMax 代表 right向左移动时的最高长度，max 代表积水量；

　　　　　　c、当 left <= right 时进行循环，

　　　　　　　　　　若 leftMax < rightMax 时， max += leftMax - height[left++]; 

　　　　　　　　　　否则 max += rightMax - height[right--];

　　　　　　意思是，取最左边与最右边的短板，若左边为短板，则计算左边短板与当前遍历的左边下标板块的积水量。否则计算右边短板与当前的右边下标的积水量。

　　　　　　　

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