您现在的位置是:首页 > Javascript
当前栏目
用「单调栈」解决“攒青豆”这类现实生活问题
2023-02-19 12:21:28 时间
问题描述
攒青豆
现有 n 个宽度为 1 的柱子,给出 n 个非负整数依次表示柱子的高度,排列后如下图所示,此时均匀从上空向下撒青豆,计算按此排列的柱子能接住多少青豆。(不考虑边角堆积)
输入格式
输入每根柱子高度的数组
输出格式
输出一个整数,表示最大能接住多少青豆
输入样例:
输出样例:
解题思路
通过单调栈找到每根柱子左边第一个比它高的位置,把两根柱子之间的青豆数累加起来,栈内元素是成递减的顺序保存的。
- 首先比较当前栈顶元素是否小于当前柱子高度,如果小于栈顶就继续入栈,否则就要找到把栈弹出到第一个比当前柱子高的位置,栈内元素存的数组下标位置,所以可以通过当前下标值与之前的值相减得到宽度差
- 使用Last变量记录上一个弹出栈顶的元素高度,因为可以计算两个柱子之间的高度差,每次弹出柱子都要更新一次Last
- 最后判断栈是否为空,不空的话需要加上左边柱子比当前柱子高的之间大小
相关代码
运行效果
在线运行
访问下方链接可以直接在线运行:https://1024code.com/codecubes/KzFluKB
总结
今天主要分享了对攒青豆的题目理解,有错误的地方欢迎大家指出,共同进步!!
本文转载自微信公众号「 程序员升级打怪之旅」,作者「王中阳Go」,可以通过以下二维码关注。
转载本文请联系「 程序员升级打怪之旅」公众号。
相关文章
- Node.js 模块化你所需要知道的事
- 初识 D3.js :打造专属可视化
- knockoutjs如何动态加载外部的file作为component中的template数据源
- NodeJs和NPM的基本操作
- 使用 System.Text.Json 时,如何处理 Dictionary 中 Key 为自定义类型的问题
- 如何使用 System.Text.Json 序列化 DateTimeOffset 为 Unix 时间戳
- javascript使用正则表达式替换或者捕获子字符串
- FastAPI从入门到实战(14)——JSON编码兼容与更新请求
- node与浏览器中的cookie
- 使用JSONPath解析json数据
- JS函数hook
- JS代码之混淆
- JS代码之还原
- JavaScript中的二进制数据
- rollup.js 初体验
- vivo悟空活动中台-打造 Nodejs 版本的MyBatis
- 前端科普系列(3):CommonJS 不是前端却革命了前端
- 前端科普系列(2):Node.js 换个角度看世界
- 探究JS V8引擎下的“数组”底层实现
- JavaScript 引擎 V8 执行流程概述