从单调栈面试题延伸:单调栈和单调队列,各解决哪类最值问题
同批的真题复盘用单调栈解了「区间最小值 × 区间和」那道笔试题,把那道题的推导讲透了。这篇把镜头拉远:单调栈还有个兄弟叫单调队列,两者名字像、都靠「单调性」吃饭,管的却是两类不同的最值问题。搞清楚「哪类问题用哪个结构」,比背任何模板都重要。
同批的真题复盘用单调栈解了「区间最小值 × 区间和」那道笔试题,把那道题的推导讲透了。这篇把镜头拉远:单调栈还有个兄弟叫单调队列,两者名字像、都靠「单调性」吃饭,管的却是两类不同的最值问题。搞清楚「哪类问题用哪个结构」,比背任何模板都重要。
同批的真题复盘讲了「至多翻转 m 次求最长连续相同子串」这一道题的完整推导;这篇我们把镜头拉远,看滑动窗口这个题型的完整谱系:定长、变长最值、至多 K 个约束,三类看起来毫不相干的题,其实共用同一副骨架。
同批的真题复盘逐行排查了一份「找最后一个等于目标值」的错误二分代码,那份代码这里不再展开。这篇把镜头拉远:二分查找不是一段要背的代码,而是一个有三个自由度的模板族。自由度想清楚,「找第一个」「找最后一个」「插入位置」「旋转数组」「山峰数组」全是同一台机器拧不同的螺丝。