程序地带

接雨水


题意

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


解题思路

每颗柱子的储水量是其左右两边最大高度的较小值减去自身高度


方法一

开辟两个数组,分别存储当前柱子左右两侧的最大值


方法二
维护一个递减栈,如果当前柱子高度大于栈顶柱子高度,则栈顶柱子储水量取决于,当前柱子和其前一个柱子注意宽度,栈内存索引

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_46313750/article/details/111246284

随机推荐

2021-01-20 图片压缩

2021-01-20 图片压缩

前言项目中用到了华为云的ocr,但是识别速度过慢,问了客服了解到可能有几个原因1、图片链接的话存在网络传输问题2、图片过大问题3、服务器网络带宽问题这里我主要处理2...

bb加油 阅读(806)

ELK-1.5亿数据处理完整过程

#filebeat配置filebeat.yml-源文件类型、路径、encoding(编码为utf-8可以忽略)-输出地方logstash或ESfilebeat启动命令-filebeat.exe-e-c...

提莫_ 阅读(429)