42. 接雨水

发表评论
326 views

 ›
42. 接雨水

官方链接

https://leetcode-cn.com/problems/trapping-rain-water/

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

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。

示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

解法一 暴力解法

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

        int area = 0;
        for(int i = 0; i < height.length; i++) {
            int left = 0;
            for(int j = 0; j <= i; j++) {
                left = Math.max(left, height[j]);
            }
            int right = 0;
            for (int k = i; k <= height.length - 1; k++) {
               right = Math.max(right, height[k]);
            }
            area += Math.min(left, right) - height[i];
        }
        return area;
    }
}

解法二 双指针法

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

        if (height.length <= 0) {
            return 0;
        }
        int area = 0;
        int left = 0;
        int right = height.length - 1;
        int maxLeft = height[left];
        int maxRight = height[right];
        while (left < right) {
            if (maxLeft < maxRight) {
                area += maxLeft - height[left];
                left++;
                maxLeft = Math.max(maxLeft, height[left]);
            } else {
                area += maxRight - height[right];
                maxRight = Math.max(maxRight, height[--right]);
            }
        }
        return area;
    }
}

解法三 DP

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

        int area = 0;
        int[] left = new int[height.length];
        int[] right = new int[height.length];

        for (int i = 0; i < height.length; i++)
            left[i] = i == 0 ? height[i] : Math.max(left[i-1], height[i]);
        for (int i = height.length - 1; i >= 0; i--)
            right[i] = i == height.length - 1 ? height[i] : Math.max(right[i+1], height[i]);

        for (int i = 0; i < height.length; i++) {
            area = Math.min(left[i], right[i]) - height[i];
        }
        return area;
    }
}

解法四 stack

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

        int area = 0, current = 0;
        Stack<Integer> stack = new Stack<Integer>();

        while (current < height.length) {
            while (!stack.isEmpty() && height[current] > height[stack.peek()]) {
                int top = stack.pop();
                if (stack.isEmpty()) break;
                int distance = current - 1 - stack.peek();
                int boundHeight = Math.min(height[current], height[stack.peek()]) - height[top];
                area += distance * boundHeight;
            }
            stack.push(current++);
        }
        return area;
    }
}