42. Trapping Rain Water

难度: Hard

题目描述

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.

 

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) 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.

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9

 

Constraints:

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

解题思路

代码实现

解决方案

java

class Solution {
    public int trap(int[] height) {

        int left = 0;
        int right = height.length - 1;

        int res = 0;
        //找到左右侧不为0的元素
        while (left < right) {
            if (height[left] != 0 && height[right] != 0) {
                break;
            }
            if (height[left] == 0) {
                left++;

            }
            if (height[right] == 0) {
                right--;
            }

        }
        int preMinHeight = 0;
        while (left < right) {
            int minHeight = Math.min(height[left], height[right]);
            int tempArea = (right - left - 1) * (minHeight - preMinHeight);
            if (tempArea == 0) {
                break;
            }

            for (int i = left + 1; i < right; i++) {
                if (preMinHeight == 0) {
                    if (height[i] != 0) {
                        tempArea -= Math.min(minHeight, height[i]) - preMinHeight;
                    }
                } else {
                    if (height[i] > preMinHeight) {
                        tempArea -= Math.min(minHeight, height[i]) - preMinHeight;
                    }
                }
            }
            res += tempArea;
            preMinHeight = minHeight;
            if (height[left] < height[right]) {
                for (int i = left + 1; i < right; i++) {
                    if (height[i] > height[left]) {
                        left = i;
                        break;
                    }
                    if (i == right - 1) {
                        return res;
                    }
                }
            } else if (height[left] > height[right]) {
                for (int i = right; i > left; i--) {
                    if (height[i] > height[right]) {
                        right = i;
                        break;
                    }
                    if (i == left + 1) {
                        return res;
                    }
                }
            } else {
                for (int i = left + 1; i < right; i++) {
                    if (height[i] > height[left]) {
                        left = i;
                        break;
                    }
                    if (i == right - 1) {
                        return res;
                    }
                }
                for (int i = right - 1; i > left; i--) {
                    if (height[i] > height[right]) {
                        right = i;
                        break;
                    }
                    if (i == left + 1) {
                        return res;
                    }
                }

            }

        }

        return res;

    }

}