Increasing/ Decreasing Stack
2024-09-25 05:32:58
对于此类问题:
对于元素nums[i],找出往左/右走第一个比它小/大的数字
我们常常用递增栈/递减栈实现。
递增栈实现第一个比它小
递减栈实现第一个比它大
Example: 2 1 5 6 2 3
stack: 保证栈是递增的顺序,因此每个数进来之前先删除栈里比它大的数字。
因此每个数,当它被pop出来时,它在栈里的前一个元素是左边第一个比它小的数,将它pop出来的数是右边第一个比它小的数。
(1) 2
(2) 1 (2被1pop出来,2左边第一个比它小的没有,右边第一个比它小的是1)
(3) 1 5
(4) 1 5 6
(5) 1 2 (5, 6 被 2 pop出来。对于5,左边第一个比它小的是1,右边第一个比它小的是2。对于6,左边第一个比它小的是5,右边第一个比它小的是2)
对于每个元素,因为只进栈出栈一次,所以总体的时间复杂度是O(n)
最新文章
- 纯HTML+CSS带说明的黄色导航菜单
- LeetCode124:Binary Tree Maximum Path Sum
- 4.kvm克隆虚拟机
- zedboard VmodCAM 图像采集 HDMI输出显示
- mysql查看'datadir'目录
- 【原创】MapReduce编程系列之表连接
- asp.net动态设置button的Text,Enabled属性,向后台传递参数
- python 10 min系列三之小爬虫(一)
- BarChart控件的使用
- CentOS 6 NFS的安装配置
- 你需要了解的 Core Spotlight
- bootstrap轮播和百叶窗
- Xshell 链接 Could not connect to '192.168.80.129' (port 22): Connection failed
- Matrix Completion with Noise
- MySQL优化之推荐使用规范
- OpenCV-Python入门教程5-阈值分割
- findStr
- GDAL对TIF创建内建金字塔一个问题
- Redis Desktop Manager连接Redis
- geoserver 常见问题笔记