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)
blank

相关推荐

  • 深入了解ASMM

    深入了解ASMM每一个Oracle的初学者在入门阶段都会接触到SGA/PGA的知识,如果是从10g开始学习那么会多或少会对ASMM有所了解,从使用的角度来说ASMM的出现极大地简化了Oracle内存初始化参数的设置,在ASMM的使用上高级DBA和初学者不会有太大的差别;很多人因此而认为ASMM极大程度地减少了数据库对于专业DBA的依赖:如果我们有一个足够智能的DB,那么为什么还要花费金钱雇佣…

  • jni断点调试「建议收藏」

    jni断点调试「建议收藏」jni断点调试

  • Linux nmap命令整理

    Linux nmap命令整理nmap–iflist:查看本地主机的接口信息和路由信息-A:选项用于使用进攻性方式扫描-T4:指定扫描过程使用的时序,总有6个级别(0-5),级别越高,扫描速度越快,但也容易被防火墙或IDS检测并屏蔽掉,在网络通讯状况较好的情况下推荐使用T4-oXtest.xml:将扫描结果生成test.xml文件,如果中断,则结果打不开-oAtest.xml:将扫描结果生成test.xml文件,中断后,结果也可保存-oGtest.txt:将扫描结果生成test…

  • win10更改pip源方法

    win10更改pip源方法win10更改pip源win10安装TensorFlow卡崩具体做法win10安装TensorFlow卡崩更改为国内清华大学镜像源,即可。具体做法在c:\user(或者用户)\电脑的用户名\,目录下创建一个命名为“pip”的文件夹(如:C:\Users\Administrator\pip),在该文件夹下创建一个命名为“pip.ini”的文件,在该文件中写入以下内容:[global]in…

  • Windows DIB文件操作具体解释-4.使用DIB Section

    Windows DIB文件操作具体解释-4.使用DIB Section

  • lm算法的实现方法_信赖域算法

    lm算法的实现方法_信赖域算法完整文章请查看这里。转载请注明出处:本文来自learnhard的博客:http://www.codelast.com/ & http://blog.csdn.net/learnhard/,并保持文章的完整性。 LM算法可用于解决非线性最小二乘问题。多用于曲线拟合等场合。LM算法的实现并不难,这里不讨论使用MATLAB等工具直接得到结果的过程,使用那些工具对于算法编程能力的提高无任何益处。 LM算法

发表回复

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

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