发布于2021-02-07
上次编辑2021-04-19
栈与队列#
单调栈#
对于给定的序列 \(s\)，当遍历到 \(s[i]\) 时，对于 \(s[i+1:]\) 中的元素而言，
- \(s[:i]\) 中 小于等于 \(s[i]\) 的元素没有用 \(\Rightarrow\) 单调递减栈
- \(s[:i]\) 中 大于等于 \(s[i]\) 的元素没有用 \(\Rightarrow\) 单调递增栈
单调队列#
问题可能限制了求解的区间范围或者元素数量，如获取离当前元素最近的几个元素中满足条件的元素，但是单调栈保存了当前元素之前所有满足条件的元素，所以可以使用队列移除最前面不在范围内的元素。
例题#
返回顶部
在手机上阅读