42. 接雨水(leetcode)

LXL's Blog / 2024-09-23 / 原文

https://leetcode.cn/problems/trapping-rain-water/description/
大厂经典题,接雨水
暴力双指针->预处理优化->单调栈

暴力:

class Solution {
    public int trap(int[] height) {
        // 暴力解法:
        // 枚举每一个柱子为底,双指针寻找左右最高的柱子,这样就找到了一个凹槽
        // 找到凹槽后累加答案
        int res=0;
        for(int i=0;i<height.length;i++)
        {
            int maxL=i,maxR=i;
            for(int l=i-1;l>=0;l--)
                if(height[l]>=height[maxL])maxL=l;
            for(int r=i+1;r<height.length;r++)
                if(height[r]>=height[maxR])maxR=r;

            // 获得左右最高柱子后,即明确了以i为底的列的雨水高度
            int h = Math.min(height[maxL],height[maxR])-height[i];
            // int h = Math.min(lHeight, rHeight) - height[i];
            if(h>0) res+=h; // 左右没有比i高的,h会小于0
        }
        return res;
    }
}

预处理优化:

class Solution {
    public int trap(int[] height) {
        // 预处理解法:
        int res=0;
        // 存储每个柱子左右最高(包括自己)的柱子高度,类似于前缀和优化(前缀最大值与后缀最大值),但是公式上类似于dp
        int[] maxL=new int[height.length];
        int[] maxR=new int[height.length];
        // 预处理每个柱子左边的最高高度
        maxL[0]=height[0]; // 左边没有比自己搞的了,就用自己高度
        for(int i=1;i<height.length;i++)
        {
            maxL[i]=Math.max(height[i],maxL[i-1]);
        }
        maxR[height.length-1]=height[height.length-1]; // 右边没有比自己高的了
        for(int i=height.length-2;i>=0;i--)
        {
            maxR[i]=Math.max(height[i],maxR[i+1]);
        }
        for(int i=0;i<height.length;i++)
        {
            // 获得左右最高柱子后,即明确了以i为底的列的雨水高度
            int h = Math.min(maxL[i],maxR[i])-height[i];
            res+=h; // h>=0,不用判断
        }
        return res;
    }
}

单调栈

class Solution {
    public int trap(int[] height) {
        // 单调栈解法:
        // 枚举每一个柱子为底部,左右第一个高于底部的柱子,围城的凹槽,累计答案(横向求解)
        // 利用当前枚举的右边第一个高的柱子right,与栈top作为底,利用单调递增
        // 使用栈后面的元素作为left来计算凹槽面积
        // 如此一个凹槽一个凹槽的计算即可
        int res=0;
        Deque<Integer> st = new ArrayDeque<>();
        for(int i=0;i<height.length;i++)
        {
            // 当前枚举的柱子比过去遍历的柱子要高,则是当前柱子右边第一个高的柱子
            while(!st.isEmpty() && height[i] >= height[st.peek()])
            {
                int mid = height[st.pop()];
                if(st.isEmpty()) break;
                int left=st.peek();
                int h=Math.min(height[i],height[st.peek()])-mid;
                res+= h * (i-left-1);
            }
            st.push(i);// 当前柱子不是右边第一个高的柱子
        }
        return res;
    }
}