LeetCode42 接雨水

问题描述:给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
例:输入: [0,1,0,2,1,0,1,3,2,1,2,1];输出: 6
LeetCode42 接雨水
思路

  • 暴力法(按列求解)
  • 双指针
//java
//暴力法
class Solution {
    public int trap(int[] height) {
        int len = height.length;
        if(len <= 2) return 0;
        int maxleft, maxright;
        int rain = 0;
        for(int i = 0; i < len; ++i){
            maxleft = maxright = 0;
            for(int j = i; j >= 0; --j){//找到左边最大高度
                maxleft = Math.max(maxleft, height[j]);
            }
            for(int j = i; j < len; ++j){//找到右边最大高度
                maxright = Math.max(maxright, height[j]);
            }
            int cmax = Math.min(maxleft, maxright);
            rain += (cmax > height[i]) ? cmax - height[i] : 0;//只有两边最小最大高度比当前列高,该列上才可能有水存在
        }
        return rain;
    }
}

//暴力优化,空间换时间
class Solution {
    public int trap(int[] height) {
        int len = height.length;
        if(len <= 2) return 0;
        int maxleft, maxright;
        int rain = 0;
        int[] lefth = new int[len];//定义两个数组先把每个位置左右两边的最高高度保存下来
        int[] righth = new int[len];
        lefth[0] = height[0];
        for(int i = 1; i < len; ++i){
            lefth[i] = Math.max(lefth[i-1], height[i]);
        }
        righth[len-1] = height[len-1];
        for(int i = len - 2; i >= 0; --i){
            righth[i] = Math.max(righth[i+1], height[i]);
        }
        for(int i = 0; i < len; ++i){
            int cmax = Math.min(lefth[i], righth[i]);
            rain += (cmax > height[i]) ? cmax - height[i] : 0;
        }
        return rain;
    }
}

//栈
class Solution {
    public int trap(int[] height) {
        int len = height.length;
        if(len <= 2) return 0;
        int rain = 0;
        Stack<Integer> s = new Stack<>();
        for(int index = 0; index < len; ++index){
            while(!s.isEmpty() && height[s.peek()] < height[index]){//一旦遇到比自己大的元素,表明可能与前一个元素(比栈顶元素大)构成了水槽(相等时不构成)
                int top = s.peek();
                s.pop();
                if(s.isEmpty()) break;
                int d = index - s.peek() - 1;
                rain += d * (Math.min(height[s.peek()], height[index]) - height[top]);//出栈元素上的水量
            }
            s.push(index);
        }
        return rain;
    }
}

//双指针
class Solution {
    public int trap(int[] height) {
        int len = height.length;
        if(len <= 2) return 0;
        int left = 0;
        int right = 1;
        int rain = 0;
        while(left < len && right < len){
            if(height[right] >= height[left]){
                rain += Math.min(height[left], height[right]) * (right - left - 1);
                ++left;
                while(left < right){
                    rain -= height[left++];
                }
            }
            ++right;
        }
        right = len - 1;
        int left1 = right - 1;
        while(left < right){
            if(height[left1] >= height[right]){
                rain += Math.min(height[left1], height[right]) * (right - left1 - 1);
                --right;
                while(left1 < right){
                    rain -= height[right--];
                }
            }
            --left1;
        }
        return rain;
    }
}
LeetCode42 接雨水LeetCode42 接雨水 Leo木 发布了29 篇原创文章 · 获赞 0 · 访问量 679 私信 关注
上一篇:EasyUI Messager的show基本使用


下一篇:如何在一台计算机上安装多个 JDK 版本