LeetCode--042--接雨水(java版)

╰半橙微兮° 2021-12-16 09:49 130阅读 0赞

给定 *n* 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

![rainwatertrap.png][]

上面是由数组 \[0,1,0,2,1,0,1,3,2,1,2,1\] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 **感谢 Marcos** 贡献此图。

**示例:**

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
    输出: 6

每次只比较两端的高度，左边小于右边，则在左边比较当前和leftMax的差值,left++,..........right--;

1 class Solution {
     2     public int trap(int[] height) {
     3         int left = 0;
     4         int right = height.length-1;
     5         int rightMax = 0;
     6         int leftMax = 0;
     7         int res = 0;
     8         while(left < right){
     9             if(height[left] < height[right]){
    10                 leftMax = Math.max(height[left],leftMax);
    11                 res += leftMax - height[left];
    12                 left++;
    13             }else{
    14                 rightMax = Math.max(height[right],rightMax);
    15                 res += rightMax - height[right];
    16                 right--;
    17             }
    18         }
    19         return res;
    20     }
    21 }

2019-03-1019:21:32

转载于:https://www.cnblogs.com/NPC-assange/p/10506554.html

[rainwatertrap.png]: /images/20211214/d8e803a62ccd4ceda94ebef192e58001.png

发表评论取消回复

表情：

评论列表（有 0 条评论，130人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode - 42 接雨水

目录题目来源题目描述示例提示题目解析算法源码 -------------------- 题目来源 [42. 接雨水 - 力扣（LeetCode

电玩女神/ 2023年09月24日 23:01/ 0 赞/ 70 阅读

相关 LeetCode 图解 | 42. 接雨水

点击关注上方“图解面试算法”，设为“置顶或星标”，一起刷 LeetCode。 ![format_png][] 作者：ioc 今天的题目来源于 LeetCode 中第

r囧r小猫/ 2023年03月12日 12:27/ 0 赞/ 113 阅读

相关【leetcode 42】接雨水 js

【leetcode 42】接雨水题目给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。示例 1： ![im

约定不等于承诺〃/ 2022年11月13日 11:21/ 0 赞/ 188 阅读

相关 LeetCode 42. 接雨水

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

深藏阁楼爱情的钟/ 2022年10月31日 04:27/ 0 赞/ 187 阅读

相关 leetcode42接雨水

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

亦凉/ 2022年10月06日 04:57/ 0 赞/ 207 阅读

相关 LeetCode42. 接雨水

难度：困难题目描述： > 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。示例 1： ![在这里插入图片描述]

Bertha 。/ 2022年09月08日 10:30/ 0 赞/ 175 阅读

相关 leetcode:42.接雨水

题目: 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 ![在这里插入图片描述][2018112901354174

蔚落/ 2022年04月13日 10:10/ 0 赞/ 233 阅读

相关 LeetCode 【42.接雨水】

LeetCode 接雨水题目描述 : 给定 n 个非负整数表示每个宽度为1 的主机的高度图，计算按此排列的主子，下雨之后能接多少雨水。 ![53526896.jpg

深碍√TFBOYSˉ_/ 2022年04月13日 09:46/ 0 赞/ 208 阅读

相关 LeetCode--042--接雨水(java版)

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 ![rainwatertrap.png][] 上面是由数组 \[0,1,

╰半橙微兮°/ 2021年12月16日 09:49/ 0 赞/ 131 阅读

相关 Leetcode: 43. 接雨水

题目描述：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 ![806400-20190710211430776-147

ゞ浴缸里的玫瑰/ 2021年10月29日 08:28/ 0 赞/ 262 阅读