我要招人

去企业版

首页 > 试题广场 >

收集雨水

[编程题]收集雨水

热度指数：9797 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给出n个数字，表示一个高程图，高程图中每一条的宽度为1，请计算下雨之后这个地形可以存储多少水

例如

给出[0,1,0,2,1,0,1,3,2,1,2,1],返回6.

上面的高程图用数组[0,1,0,2,1,0,1,3,2,1,2,1]表示。在这种情况下，6个单位的雨水（蓝色部分）被存储。

示例1

输入

[0,1,0,2,1,0,1,3,2,1,2,1]

输出

算法知识视频讲解

Java

tornado123

/** 收集雨水 - 栈
 * @author lt
 * @data 2020/9/20 22:04
 */
public class CollectingRainwater {
    /**
     *
     * @param A int整型一维数组
     * @return int整型
     */
    public int trap (int[] A) {
        // result 是最终结果
        int result = 0;
        int max = 0;
        int len_a = A.length;
        for (int i = 0; i < len_a; i++) {
            if (A[i] > max) {
                max = A[i];
            }
        }
        // 相当于逐层升高水平线
        while (max > 0) {
            int i = 0, j = len_a -1;
            // 去除最左边的 0 节点
            while (i < len_a && A[i] == 0) {
                i++;
            }
            // 去除最右边的 0 节点
            while (j >= i && A[j] == 0) {
                j--;
            }
            // 统计符合要求的 0 节点数
            while (i <= j) {
                if (A[i] == 0) {
                    result ++;
                }else {
                    A[i] -= 1;
                }
                i++;
            }
            max --;
        }
        return result;
    }

    public static void main(String[] args) {
        int[] num = new int[]{0,1,0,2,1,0,1,3,2,1,2,1};
        System.out.println(new CollectingRainwater().trap(num));
    }
}

发表于 2020-09-20 23:31:20 回复(0)

Java

科学xx

    public int trap (int[] A) {
        if (A == null || A.length == 0){
            return 0;
        }
        int sum = 0;
        int len = A.length;
        //左边最大值
        int[] leftMax = new int[len];
        leftMax[0] = A[0];
        for (int i = 1; i < len; i++) {
            leftMax[i] = Math.max(A[i],leftMax[i-1]);
        }
        //右边最大值
        int[] rightMax = new int[len];
        rightMax[len - 1] = A[len - 1];
        for (int i = len - 2; i >= 0; i--) {
            rightMax[i] = Math.max(A[i],rightMax[i+1]);
        }
        //比较最小值减去当前坐标累加
        for (int i = 0; i < len; i++) {
            sum += (Math.min(leftMax[i],rightMax[i]) - A[i]);
        }
        return sum;
    }

public int trap (int[] A) {
       if (A == null || A.length == 0){
            return 0;
        }
        int sum = 0;
        int left = 0, right = A.length - 1;
        int leftMax = 0,rightMax = 0;
        //左右逼近
        while (left < right){
            //比较左右较小的
            if (A[left] < A[right]){
                //计算左边,大就替换，小就计算值
                if (leftMax <= A[left]){
                    leftMax = A[left];
                }else {
                    sum += (leftMax - A[left]);
                }
                left++;
            }else {
                if (rightMax <= A[right]){
                    rightMax = A[right];
                }else {
                    sum += (rightMax - A[right]);
                }
                right--;
            }
        }
        return sum;
    }

编辑于 2020-09-20 14:47:45 回复(0)

Java

key、L

class Solution {
    public int trap(int[] A) {
        int len = A.length;
        //最左和最右没有雨水,把雨水总和看成除了最左和最右两个元素之外
        //的其他元素上方的雨水总和
        int rain = 0;
        for(int i = 1; i <= len - 2; i++){
            int leftMax = getMax(A, 0, i - 1);
            int rightMax = getMax(A, i + 1, len - 1);
            if(leftMax > A[i] && rightMax > A[i]){
                rain += Math.min(leftMax, rightMax) - A[i];
            }
        }
        return rain;
    }
    public int getMax(int[] height, int begin, int end){
        int max = Integer.MIN_VALUE;
        for(int i = begin; i <= end; i++){
            if(height[i] > max)
                max = height[i];
        }
        return max;
    }
}

发表于 2020-02-13 18:36:35 回复(0)

Java

为你扣下F键

public class Solution {
    public int trap(int[] A) {
        int res = 0;
        int i = 0;
        int j = A.length - 1;
        int left_height = 0;// 记录i的左边的最大高度
        int right_height = 0;// 记录j的右边的最大高度
        while (i <= j) {
            // 左边的高度小于右边，则i处的积水由左边决定
            if (left_height < right_height) {
                res += Math.max(0, left_height - A[i]);
                // 更新左边的最大高度
                left_height = Math.max(left_height, A[i]);
                i++;
            }
            // 右边的高度小于左边，则j处的积水由右边决定
            else {
                res += Math.max(0, right_height - A[j]);
                // 更新右边的最大高度
                right_height = Math.max(right_height, A[j]);
                j--;
            }
        }
        return res;
    }
}

编辑于 2018-12-10 22:54:31 回复(0)

Java

The_Flash

import java.util.*;
public class Solution {
    public int trap(int[] A) {
        int n = A.length;
        int[] maxLeft = new int [n];//找出每个柱子左边最高的
        int[] maxRight = new int [n];//找出每个柱子右边最高的
        
        for(int i=1; i<n; i++){
            maxLeft[i] = Math.max(maxLeft[i-1], A[i-1]);
            maxRight[n-1-i] = Math.max(maxRight[n-i], A[n-i]); 
        }
        
        int sum = 0;
        //从左到右找出每个柱子左右最低的部分，再减去当下柱子本身，得出深度
        for(int i=1; i<n; i++){
            int height = Math.min(maxLeft[i], maxRight[i]);
            if(height > A[i]){
                sum = sum + height - A[i];
            }
        }
        return sum;
    }
}

发表于 2017-12-31 12:46:11 回复(0)

Java

Eliefly

磕磕绊绊写出来了...再碰上的话写出来也难

import java.util.Stack;

public class Solution {
    public int trap(int[] A) {
        int len = A.length;
        Stack<Integer> stack = new Stack<>();
        int trap = 0;
        for (int i = 0; i < len; i++) {
            int hCur = A[i];
            int hPre = stack.empty() ? 0 : A[stack.peek()];
            if (hCur > hPre && !stack.empty()) {
                hPre = A[stack.pop()];
                int left = stack.empty() ? 0 : stack.peek();
                int distance;
                if (A[left] > hCur) {
                    distance = hCur - hPre;
                } else {
                    if (stack.size() == 1) {
                        stack.pop();
                    }
                    distance = A[left] - hPre;
                }
                 if (distance > 0) {
                     trap = trap + distance * (i - left - 1);
                 }
                i--;
            } else if (hCur == hPre && !stack.empty()) {
                stack.pop();
                stack.push(i);
            } else {
                stack.push(i);
            }
        }
        return trap;
    }
}

编辑于 2017-09-29 11:28:49 回复(0)

Java

左神的小幺

左神思路：使用辅助数组，把时间复杂度从O(n^2)降到O(n)。
public static int rainWater(int[] arr) {
		if (arr == null || arr.length == 0) {
			return 0;
		}
		int[] left = new int[arr.length];
		int[] right = new int[arr.length];
		left[0] = arr[0];
		right[arr.length - 1] = arr[arr.length - 1];
		int sum = 0;
		for (int i = 1; i < arr.length; i++) {
			left[i] = Math.max(left[i - 1], arr[i]);
		}
		for (int i = arr.length - 2; i >= 0; i--) {
			right[i] = Math.max(right[i + 1], arr[i]);
		}
		for (int i = 0; i < arr.length; i++) {
			int min = Math.min(left[i], right[i]);
			if (arr[i] < min) {
				sum += (min - arr[i]);
			}
		}
		return sum;
	}

发表于 2017-08-11 20:37:18 回复(0)

Java

城市里的养猫者

Keep track of the maximum height from both forward directions backward directions, call them leftmax and rightmax.

public int trap(int[] A){ int a=0; int b=A.length-1; int max=0; int leftmax=0; int rightmax=0; while(a<=b){
        leftmax=Math.max(leftmax,A[a]);
        rightmax=Math.max(rightmax,A[b]); if(leftmax<rightmax){ max+=(leftmax-A[a]); // leftmax is smaller than rightmax, so the (leftmax-A[a]) water can be stored a++;
        } else{ max+=(rightmax-A[b]);
            b--;
        }
    } return max;
}