【LeetCode】42.接雨水

题目链接

42. 接雨水

题目描述

解题思路

暴力法（按列求取雨水值）

因为首尾元素不可能存在雨水，所以可以不用考虑首尾元素。

对于剩余的每个元素，分别计算从该元素开始，从左和从右开始开始的最大值，然后当前元素对应的能够接的雨水值 = Math.min(maxLeft，maxRight) - height[i];

时间复杂度：O(n2)

空间复杂度：O(1)

动态规划

在暴力法中，我们每次都要计算当前坐标对应的左边最大值maxLeft以及右边最大值maxRight，所以直接导致时间复杂度为O(n2)，然而这些值都是固定的，所以我们可以提前利用两个数组maxleft[]以及maxRight[]记录每个下标对应的左边最大值和右边最大值。

时间复杂度：O(n)

空间复杂度：O(n)

单调栈

单调递减栈，栈中存放的是索引值，因为通过索引值也可以得到height数组中的元素值。

如果当前索引对应的height数组值 <= 前一个索引对应的height数组值，那么接不雨水。

如果当前索引对应的height数组值 > 前一个索引对应的height数组值，那么才有可能接到雨水（注意是有可能，而不是一定，只有同时满足单调栈不为空的时候才能接到雨水）

参考下图就一目了然，利用单调栈也可以理解为是按行计算雨水值

如果当前下标对应的height数组值小于栈顶元素则入栈。

如果当前下标对应的height数组值大于栈顶元素且当前stack不为空，则说明此时这种情况存在雨水值，雨水值的计算方式如下：

首先记录value = 弹栈元素对应的height数组值
其次记录Math.min（新的栈顶元素对应的height数组值，以及当前索引对应的height数组值），然后减去value值，则为水坑对应的高度。
水坑的宽度 = 当前索引 - 新的栈顶元素。

参考资料

AC代码

暴力法

class Solution {
    //按照每列的雨水数目计算结果
    public int trap(int[] height) {
        int ans = 0;
        //因为开头结尾不会有雨水，所以可以不用考虑
        for(int i = 1; i < height.length - 1; i++){
            int maxLeft = height[i];
            int maxRight = height[i];
            for(int j = i - 1; j >= 0; j--){
                if(height[j] > maxLeft){
                    maxLeft = height[j];
                }
            }
            for(int j = i + 1; j < height.length; j++){
                if(height[j] > maxRight){
                    maxRight = height[j];
                }
            }
            ans += Math.min(maxLeft,maxRight) - height[i];
        }
        return ans;
    }
}

动态规划

class Solution {
    public int trap(int[] height) {
        if(height.length == 0) return 0;
        int maxLeft[] = new int[height.length];
        int maxRight[] = new int[height.length];
        int ans = 0;
        maxLeft[0] = 0;
        for(int i = 1; i < height.length; i++){
            maxLeft[i] = Math.max(height[i - 1],maxLeft[i-1]);
        }
        maxRight[height.length-1] = 0;
        for(int i = height.length - 2; i >= 0; i--){
            maxRight[i] = Math.max(height[i+1],maxRight[i+1]);
        }
        for(int i = 1; i < height.length; i++){
            int h = Math.min(maxLeft[i],maxRight[i]);
            if(h > height[i]){
                ans += h - height[i];
            }
        }
        return ans;
    }
}

//改进版动态规划
class Solution {
    public int trap(int[] height) {
        if(height.length == 0) return 0;
        int maxRight[] = new int[height.length];
        int ans = 0;
        int maxLeft = 0;
        maxRight[height.length-1] = 0;
        for(int i = height.length - 2; i >= 0; i--){
            maxRight[i] = Math.max(height[i+1], maxRight[i+1]);
        }
        for(int i = 1; i < height.length; i++){
            maxLeft = Math.max(maxLeft,height[i - 1]);
            int h = Math.min(maxLeft,maxRight[i]);
            if(h > height[i]){
                ans += h - height[i];
            }
        }
        return ans;
    }
}

//改进版，双指针法
public int trap(int[] height) {
    int sum = 0;
    int max_left = 0;
    int max_right = 0;
    int left = 1;
    int right = height.length - 2; // 加右指针进去
    for (int i = 1; i < height.length - 1; i++) {
        //从左到右更
        if (height[left - 1] < height[right + 1]) {
            max_left = Math.max(max_left, height[left - 1]);
            int min = max_left;
            if (min > height[left]) {
                sum = sum + (min - height[left]);
            }
            left++;
        //从右到左更
        } else {
            max_right = Math.max(max_right, height[right + 1]);
            int min = max_right;
            if (min > height[right]) {
                sum = sum + (min - height[right]);
            }
            right--;
        }
    }
    return sum;
}

作者：windliang
链接：https://leetcode-cn.com/problems/trapping-rain-water/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-8/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

单调栈

class Solution {
    public int trap(int[] height) {
        Stack<Integer> st = new Stack<>();
        int ans = 0;
        for(int i = 0; i < height.length; i++){
            while(!st.isEmpty() && height[i] > height[st.peek()]){
                int index = st.pop();
                int value = height[index];
                if(st.isEmpty() == false) ans += (Math.min(height[st.peek()],height[i]) - value) * (i-st.peek()-1);
            }
            st.push(i);
        }
        return ans;
    }
}