42. 接雨水

╰半夏微凉° 2022-10-10 12:31 209阅读 0赞

> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNDkwMg_size_16_color_FFFFFF_t_70][]
> 
> 输入：height = \[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 个单位的雨水（蓝色部分表示雨水）。

class Solution {
        public int trap(int[] height) {
            /**
            类似双指针
                首先找到最大值下标,以他为分割 为 左右两部分
    
                每一部分都是这样看:
                    找最大值,找到就更新,找不到就res+=(max高度-当前高度)
             */
             int  res=0;//结果
             int maxIndex=0;//找到最大值下标
             for(int i=0;i<height.length;i++){
                 if(height[i]>height[maxIndex]){
                     maxIndex=i;
                 }
             }
    
             //看左边
             int leftMax=0;
             for(int i=0;i<maxIndex;i++){
                 if(height[i]>leftMax){
                     leftMax=height[i];
                 }else{
                     res+=(leftMax-height[i]);
                 }
             }
             //看右边
             int  rightMax=0;
             for(int i=height.length-1;i>maxIndex;i--){
                 if(height[i]>rightMax){
                     rightMax=height[i];
                 }else{
                     res+=(rightMax-height[i]);
                 }
             }
            return res;
    
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNDkwMg_size_16_color_FFFFFF_t_70]: /images/20221005/8fd2386a68d94d40bbebc043e6565c19.png

发表评论取消回复

表情：

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

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

相关阅读

相关 42.接雨水

42.接雨水题干分析解题思路 1. 暴力解法 2. 双指针优化 3. 单调栈解法 3.1 准备

悠悠/ 2024年02月25日 04:12/ 0 赞/ 76 阅读

相关 42接雨水

一、前言标签：动态规划、栈运用、双指针。问题来源LeetCode 5 难度：困难。问题链接：[https://leetcode-cn.com/problems/

川长思鸟来/ 2023年02月28日 15:25/ 0 赞/ 15 阅读

相关 LeetCode 42. 接雨水

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

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

相关 42. 接雨水

> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaX

╰半夏微凉°/ 2022年10月10日 12:31/ 0 赞/ 210 阅读

相关 leetcode42接雨水

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

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

相关 42. 接雨水

[https://leetcode-cn.com/problems/trapping-rain-water/][https_leetcode-cn.com_problems_t

╰+哭是因爲堅強的太久メ/ 2022年09月09日 11:00/ 0 赞/ 280 阅读

相关 LeetCode42. 接雨水

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

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

相关 leetcode:42.接雨水

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

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

相关 LeetCode 【42.接雨水】

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

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

相关 42. 接雨水

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

ゝ一世哀愁。/ 2021年06月10日 20:37/ 0 赞/ 372 阅读