当前位置：首页 > news >正文

单调栈：接雨水

news 来源：原创 2024/5/3 14:40:22

解法：雨水面积 = 底边长w*雨水高度h

双指针：

求每个位置的水位高度，以当前位置为中心，双指针分别向左右寻找最高边界。
h = min(lHeight, rHeight) - height[i]； w=1

动态规划：

根据已知的边界高度和当前高度比较，确定当前位置的左右边界高度，取最高的左右高度值
int[len+2][2]: 存放个位置的左边界高，右边界高；首尾设置虚拟节点表示边界，高度为0
遍历高度：左到右确定左界值。右到左确定右界值
h = min(lHeight, rHeight) - height[i]； w=1

单调栈：

栈内元素对应高度值：大到小（栈底到栈头），即栈内可确定左边界（栈内存放下标）
新加元素符合单调性：直接加入
新加元素 = 栈头旧元素: 旧元素出栈，新元素入栈（保证左侧的最右边边界）
新加元素 > 栈头旧元素：右边界确定，栈头出栈，当前栈头为左边界，计算当前凹槽高度的存水量，重复该步骤，直到满足新元素入栈条件
宽（下标间距离）*高（可存高度差）：(i-pre-1)*(Math.min(height[i],height[pre])-height[cur])

//双指针法：寻找每个位置上的可堆积的雨水高度，即左右寻找水桶的最高边界，取最低值-底部高度
class Solution {
    public int trap(int[] height) {
        int sum= 0;
        //计算每一个位置可堆积的雨水高度,叠加
         int lheight, rheight;
        for(int i = 0; i < height.length; i++){
            lheight = 0;
            rheight = 0;
            for(int l = i-1; l >= 0; l--){
                lheight = Math.max(lheight,height[l]);
            }
            for(int r = i+1; r < height.length; r++){
                rheight = Math.max(rheight,height[r]);
            }
            int get = Math.min(lheight,rheight)-height[i];
            sum += get>0? get:0;
        }
        return sum;
    }
}


//动态规划：最快，按列计算存水量
class Solution {
    public int trap(int[] height) {
        int len = height.length;
        int[][] dp = new int[len+2][2];//初始值全为0,首尾添加虚拟节点可存水高度一定为0
        int sum= 0;
        for(int left = 1; left <= len; left++){
            dp[left][0] = Math.max(dp[left-1][0],height[left-1]);//左侧高度
            int right = len+2-1-left;
            dp[right][1] = Math.max(dp[right+1][1],height[right-1]);//右侧高度
        }
        for(int i = 1; i <= len; i++){
            int get = Math.min(dp[i][0],dp[i][1])-height[i-1];
            sum += get>0?get:0;
        }
        return sum;
    }
}

//单调栈：按行计算存水量
class Solution {
    public int trap(int[] height) {
        Stack<Integer> index = new Stack<>();
        int sum = 0;
        index.push(0);
        for(int i = 1; i < height.length; i++){
            int cur = index.peek();
            while(!index.isEmpty() && height[i] >= height[cur]){
                cur = index.pop();
                if(!index.isEmpty()){
                    int pre = index.peek();
                    sum += (i-pre-1)*(Math.min(height[i],height[pre])-height[cur]);
                    cur = pre;
                }               
            }
            index.push(i);
        }
        return sum;
    }
}