单调栈、滑动窗口与哈希优化的思路与适用场景
哪些公司问过
华为2华为OD1
答案要点
- 单调栈:栈内元素单调,找左右第一个更大或更小的元素,每个元素最多进出一次,O(n)
- 滑动窗口:双指针维护连续区间,适合连续子数组或子串,要求有单调性,O(n)
- 哈希优化:记录出现次数或位置,把查找降到 O(1),用于计数、判重、查补数
- 典型题:下一个更大元素、最长无重复子串、两数之和
- 三者常结合,如滑动窗口内用哈希表统计频次
易错点
- 滑动窗口用在没有单调性的区间问题上
- 单调栈的单调方向弄反
- 只讲技巧名字,说不出对应的题型
面试官常见追问
- 滑动窗口什么时候不适用?
- 单调栈能解决什么样的问题?
- 哈希表优化的代价是什么?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 栈和队列的区别与应用68 场
- 四则运算表达式求值15 场
- 循环队列(环形缓冲区)的实现14 场
- 最长有效括号12 场
- 滑动窗口最大值与滑动平均滤波12 场
- 有效的括号(栈)11 场
- 实现支持 O(1) 获取最小值的栈9 场
- 单调栈:下一个更大元素与每日温度6 场
- 数据流的中位数(大根堆加小根堆)5 场
- 滑动窗口最大值的单调队列解法4 场