leetcode 接雨水2_code42

leetcode 接雨水2_code42题目链接给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。示例 1:输入: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 个单位的雨水(蓝色部分表示雨水)。示例 2:输入:height = [4,2,0,3,2,5]输出:9 提示:n == height.length0 <= n &lt

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

题目链接

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

示例 1:
在这里插入图片描述

输入: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 个单位的雨水(蓝色部分表示雨水)。
示例 2:

输入:height = [4,2,0,3,2,5]
输出:9
 

提示:

n == height.length
0 <= n <= 3 * 104
0 <= height[i] <= 105

题解
单调栈

class Solution { 
   
public:
    int trap(vector<int>& height) { 
   
        stack<int>stk;
        int res = 0;
        for(int i = 0;i < height.size();i ++){ 
   
            int pre = 0;
            while(!stk.empty() && height[stk.top()] <= height[i]){ 
   
                int t = stk.top();
                stk.pop();
                res += (height[t] - pre) * (i - t - 1);
                pre = height[t];
            }
            if(!stk.empty())res += (height[i] - pre) * (i - stk.top() - 1);
            stk.push(i);
        }
        return res;
    }
};
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/168996.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • jvm 调优命令_java jvm调优工具

    jvm 调优命令_java jvm调优工具直接内存是在java堆外的、直接向系统申请的内存空间。通常访问直接内存的速度会优于Java堆。因此出于性能的考虑,读写频繁的场合可能会考虑使用直接内存。

  • [Java Performance] 数据库性能最佳实践 – JPA缓存

    [Java Performance] 数据库性能最佳实践 – JPA缓存

  • 解决Discuz! info: MySQL Query Error[通俗易懂]

    解决Discuz! info: MySQL Query Error[通俗易懂]php下安装Discuz!完成后点进bbs报错:Discuz!info:MySQLQueryErrorTime:2014-11-68:23amScript:/discuz7/bbs/in

  • 如何理解掩码、反掩码、通配符「建议收藏」

    如何理解掩码、反掩码、通配符「建议收藏」反掩码、掩码和通配符的区别一、掩码在掩码中,1表示精确匹配,0表示随机1和0,永远不交叉;1永远在左边,0永远在右边;在配置IP地址以及路由的时候,会使用掩码;二、反掩码在反掩码中,1表示随机,0表示精确匹配0和1,永远不交叉;0永远在左边,1永远在右边;在路由协议的配置中,通过network命令进行网段宣告时,会使用三、通配符在统配符中,1表示随机,0表示精确匹配0和1的位置,没有任何的固定限制可以连续,可以交叉在ACL中,使用的通配符通配符掩码表CIDR子网掩码反掩

  • Jenkins学习——Jenkins是什么

    Jenkins学习——Jenkins是什么Jenkins是什么     对于Jenkins是什么,百度百科给的答案是这样的:Jenkins是一个开源软件项目,旨在提供一个开放易用的软件平台,使软件的持续集成变成可能。     通过这句话,我们可以得到这样的一个信息——Jenkins是一个开源的东东,好像跟持续集成开发有关系(然而我们并不知道持续集成开发是什么东东)。     通俗的说,就我目前的理解

  • 黑盒测试c语言用例,黑盒测试用例设计技术包括_测试用例包括什么_常用黑盒测试用例设计(4)…

    黑盒测试c语言用例,黑盒测试用例设计技术包括_测试用例包括什么_常用黑盒测试用例设计(4)…因此,可以把全部输入数据合理地划分为若干等价类,在每一个等价类中取一个数据作为测试的输入条件,这样就可以用少量的代表性测试数据,来取得较好的测试结果。黑盒测试用例设计技术包括*是指对于程序的规格说明来说,是合理的有意义的输入数据构成的集合。利用它可以检验程序是否实现预先规定的功能和性能。在具体问题中,有效等价类可以是一个,也可以是多个。有效等价类*是指对于程序的规格说明…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号