手撕算法-接雨水

描述

分析

i位置能积累的雨水量，等于其左右两边最大高度的最小值。
为了能获取i位置左右两边的最大高度。使用动态规划。
两个dp数组：

• leftMax
• rightMax

其中

• leftMax[i] 代表i位置左边的最大高度
• rightMax[i] 代表i位置右边的最大高度

初始状态：

• leftMax[0] = 0;
• rightMax[0] =0;

填充这两个dp数组。

那么i位置最终能存的雨水量为：min(eftMax[i] , rightMax[i]) – height[i]

遍历所有位置，即可得到总共能接的雨水数。

代码

服务器托管网

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int[] leftMax = new int[n];
        int[] rightMax = new int[n];

        leftMax[0] = height[0];
        for (int i = 1; i  n; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }

        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }

        int res = 0;
        for (int i =服务器托管网 0; i  n; i++) {
            res += Math.min(leftMax[i], rightMax[i]) - height[i];
        }

        return res;
    }
}

面试公司

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net

相关推荐: Java实现课程案例资源库系统 JAVA+Vue+SpringBoot+MySQL

目录 一、摘要 1.1 项目介绍 1.2 项目录屏 二、功能模块 2.1 管理员需求分析 2.2 用户需求分析 三、系统设计 3.1 业务流程设计 3.1.1 管理员业务流程设计 3.1.2 用户业务流程设计 3.1.3 首页功能模块及业务流程分析 3.1.4…