罗罗编程学习记录
本页内容 展开查看

02.9.1.4 双指针滑窗二分高频

所属:全栈开发面试题库 / 02 数据结构与算法 / 02.9 高频题单 / 02.9.1 高频题单与解题路线

本页为索引串联型题单:每题给出一句话思路、复杂度口径、易错点与本库关联页面,完整推导见关联页面。

02.9.1.4-001 两数之和 II 有序数组(LC 167)

一句话结论

数组有序,左右对撞指针:和偏小左移 l,偏大右移 r,命中返回下标。

概念解释

考点:对撞双指针;时间 O(n),空间 O(1)。

原理流程

  1. l=0, r=n-1。
  2. 按和与目标比较移动指针。
  3. 命中返回 1 基下标。

代码 / 示例

关联:数组原地操作与快慢双指针

常见误区

  • 误区:用哈希忽略有序条件;正解:有序下双指针 O(1) 空间。
  • 误区:下标返回 0 基还是 1 基混淆。

追问

  • Q:为什么不会漏解? A:有序下排除一支指针不会错过唯一解。
  • Q:有重复值? A:题目保证唯一解。

02.9.1.4-002 三数之和(LC 15)

一句话结论

排序固定一层,余下对撞双指针,固定值与命中两侧都去重。

概念解释

考点:排序 + 双指针;时间 O(n²),空间 O(1)。

原理流程

  1. 排序。
  2. i 固定,l、r 夹逼。
  3. 命中后跳过重复值。

代码 / 示例

关联:数组原地操作与快慢双指针

常见误区

  • 误区:只去重外层固定值。
  • 误区:和偏大时移动方向写反。

追问

  • Q:四数之和(LC 18)? A:两层固定 + 双指针。
  • Q:复杂度瓶颈? A:枚举 O(n²)。

02.9.1.4-003 四数之和(LC 18)

一句话结论

排序后两层固定 i、j,内层对撞双指针;各层跳过重复值,剪枝越界情况。

概念解释

考点:多层固定 + 双指针;时间 O(n³),空间 O(1)。

原理流程

  1. 排序。
  2. 两层枚举固定值。
  3. 双指针夹逼并去重。

代码 / 示例

关联:数组原地操作与快慢双指针

常见误区

  • 误区:每层重复值未跳过产生重复四元组。
  • 误区:固定层提前剪枝条件写错。

追问

  • Q:N 数之和通用框架? A:递归降维到两数之和双指针。
  • Q:复杂度随层数增长? A:O(n^{k-1})。

02.9.1.4-004 接雨水(LC 42)

一句话结论

按列算积水 = min(左最高, 右最高) - 当前高度;可预处理左右最高数组,或双指针/单调栈。

概念解释

考点:双指针/单调栈;时间 O(n),空间 O(1)(双指针)。

原理流程

  1. 维护左右最高。
  2. 矮侧指针推进算积水。
  3. 累加每格水量。

代码 / 示例

关联:单调栈与柱状图接雨水

常见误区

  • 误区:按两根高板之间整体算;正解:逐格按两侧最高短板计算。
  • 误区:当前高度高于短板时水量为负未取 0。

追问

  • Q:单调栈怎么做? A:维护递减栈,遇到更高柱弹出算凹槽积水。
  • Q:与盛水容器区别? A:容器算两板间面积,接雨水逐格累计。

02.9.1.4-005 每日温度(LC 739)

一句话结论

单调栈存待升温下标;当前温度高于栈顶则弹出并记录等待天数,栈内保持递减。

概念解释

考点:单调栈;时间 O(n),空间 O(n)。

原理流程

  1. 栈存下标。
  2. 高温弹出栈顶算天数。
  3. 当前下标入栈。

代码 / 示例

关联:单调栈与柱状图接雨水

常见误区

  • 误区:栈存温度值丢失下标。
  • 误区:相等温度也弹出;正解:相等不算升温,留在栈中。

追问

  • Q:下一个更大元素(LC 496)? A:同模板,循环数组变体补两倍长度。
  • Q:单调栈方向? A:本题递减栈找右侧更大。

02.9.1.4-006 柱状图中最大矩形(LC 84)

一句话结论

单调栈存递增高度下标;当前更矮时弹出栈顶,以该高度为矩形高,结合左右边界算宽度。

概念解释

考点:单调栈;时间 O(n),空间 O(n)。

原理流程

  1. 递增栈。
  2. 矮柱弹出算面积。
  3. 末尾补高度 0 清空栈。

代码 / 示例

关联:单调栈与柱状图接雨水

常见误区

  • 误区:宽度边界算成当前下标差;正解:弹出后新栈顶为左边界。
  • 误区:未补哨兵高度导致末尾残留。

追问

  • Q:暴力做法? A:枚举柱为高向两侧扩展 O(n²)。
  • Q:与接雨水栈法区别? A:一个求矩形面积,一个求凹槽水量。

02.9.1.4-007 有效括号(LC 20)

一句话结论

栈存左括号;遇右括号弹栈匹配对应类型,空栈或类型不符即无效;结束栈空才合法。

概念解释

考点:栈匹配;时间 O(n),空间 O(n)。

原理流程

  1. 左括号入栈。
  2. 右括号比对栈顶。
  3. 结束判空。

代码 / 示例

关联:栈基础与括号表达式求值

常见误区

  • 误区:右括号时栈空未判。
  • 误区:三种括号类型映射写反。

追问

  • Q:括号生成(LC 22)? A:回溯构造合法串,见 02.9.1.3-016。
  • Q:最长有效括号(LC 32)? A:栈或 DP,难度更高。

02.9.1.4-008 最小栈(LC 155)

一句话结论

主栈 + 辅助栈同步存当前最小值;入栈时辅助栈压入新最小值,出栈两栈同步弹。

概念解释

考点:辅助栈;push/pop/top/getMin 均 O(1),空间 O(n)。

原理流程

  1. 入栈同时压当前 min。
  2. 出栈两栈同步。
  3. getMin 取辅助栈顶。

代码 / 示例

关联:栈基础与括号表达式求值

常见误区

  • 误区:辅助栈只在更小时压入,弹出最小值时无法恢复次小。
  • 误区:出栈时辅助栈不同步。

追问

  • Q:单栈存差值做法? A:栈内存与最小值的差值,省一份空间。
  • Q:getMin 不能弹最小值? A:题目要求 pop 正常弹出。

02.9.1.4-009 搜索旋转排序数组(LC 33)

一句话结论

二分:先判断哪一半有序,目标落在有序半则收缩该半,否则走另一半;无重复值。

概念解释

考点:二分变体;时间 O(log n),空间 O(1)。

原理流程

  1. mid 取中。
  2. 比较左端判断有序半。
  3. 按目标归属收缩区间。

代码 / 示例

关联:旋转数组与部分有序

常见误区

  • 误区:整体有序二分直接套;正解:旋转后一段有序需先判段。
  • 误区:有重复值时边界判断退化(LC 81)。

追问

  • Q:含重复(LC 81)? A:两端相等时无法判有序,收缩一端,最坏 O(n)。
  • Q:找旋转点? A:二分找最小值下标。

02.9.1.4-010 排序数组查找首末位置(LC 34)

一句话结论

两次二分:找左边界(首个 >= target)与右边界(最后一个 <= target);标准边界二分模板。

概念解释

考点:边界二分;时间 O(log n),空间 O(1)。

原理流程

  1. 左边界二分收缩到首个 >= target。
  2. 右边界二分找最后一个 <= target。
  3. 校验命中后返回区间。

代码 / 示例

关联:二分模板与边界

常见误区

  • 误区:找到一个相等值就线性扩散;正解:两次二分定位边界。
  • 误区:区间开闭与收缩条件不匹配。

追问

  • Q:模板两种写法? A:闭区间 [l,r] 与左闭右开,收缩口径一致即可。
  • Q:不存在时返回? A:[-1,-1]。

02.9.1.4-011 寻找峰值(LC 162)

一句话结论

二分比较 mid 与右邻:mid 更大则峰值在左半,否则在右半;端点视为 -∞,必有峰值。

概念解释

考点:二分排除;时间 O(log n),空间 O(1)。

原理流程

  1. 比较 mid 与 mid+1。
  2. 下降则左半含峰,上升则右半含峰。
  3. 收敛到峰值下标。

代码 / 示例

关联:二分模板与边界

常见误区

  • 误区:要求全局严格最大;正解:局部峰值即可。
  • 误区:相邻相等元素处理口径。

追问

  • Q:为什么一定有峰值? A:端点 -∞,相邻变化必有局部高点。
  • Q:O(n) 扫描? A:遍历比较邻居,二分更优。

02.9.1.4-012 爱吃香蕉的珂珂(LC 875)

一句话结论

二分答案:速度 k 单调影响耗时;判定给定 k 能否在 H 小时吃完,二分最小可行 k。

概念解释

考点:二分答案;时间 O(n log max),空间 O(1)。

原理流程

  1. 速度范围 1~max(piles)。
  2. 判定函数算总耗时。
  3. 二分收缩最小可行速度。

代码 / 示例

关联:二分答案

常见误区

  • 误区:耗时用整除未向上取整;正解:每堆 (p+k-1)/k。
  • 误区:判定单调性方向写反。

追问

  • Q:二分答案适用条件? A:可行性随答案单调变化。
  • Q:其他二分答案题? A:分割数组最大值、船运货物。

02.9.1.4-013 二维矩阵搜索(LC 74)

一句话结论

矩阵每行有序且下一行首大于上一行尾;把矩阵当一维数组二分,下标映射 mid / n、mid % n。

概念解释

考点:二维二分;时间 O(log(mn)),空间 O(1)。

原理流程

  1. 一维下标范围 0~mn-1。
  2. 映射行列取元素。
  3. 二分比较收缩。

代码 / 示例

关联:二维矩阵与非数组二分

常见误区

  • 误区:行列映射算反。
  • 误区:矩阵不满足行首递增时硬套。

追问

  • Q:行列分别有序(LC 240)? A:从右上角起步消行消列。
  • Q:复杂度? A:log(mn) 次比较。

02.9.1.4-014 颜色分类(LC 75)

一句话结论

三指针原地分区:left 放 0,right 放 2,mid 扫描;遇到 0 换 left,遇到 2 换 right,1 前进。

概念解释

考点:三指针荷兰国旗;时间 O(n),空间 O(1)。

原理流程

  1. l=0, r=n-1, m=0。
  2. 0 交换 l、l++、m++。
  3. 2 交换 r、r--(m 不前移复查)。

代码 / 示例

关联:数组原地操作与快慢双指针

常见误区

  • 误区:换 2 后 m 直接前进;正解:换过来的值需复查。
  • 误区:两次计数排序覆盖,非原地交换思路。

追问

  • Q:K 种颜色? A:计数排序或多指针推广。
  • Q:与快排三路划分关系? A:同分区思想,见 02.5.2.2。

02.9.1.4-015 最长重复子数组(LC 718)

一句话结论

双序列 DP:连续匹配,相等则 dp[i][j] = dp[i-1][j-1] + 1,不等置 0;全局取最大。

概念解释

考点:连续子序列 DP;时间 O(mn),空间 O(n) 滚动。

原理流程

  1. 状态:两前缀结尾连续匹配长度。
  2. 相等继承对角线 +1。
  3. 不等清零,全局取 max。

代码 / 示例

关联:子序列问题

常见误区

  • 误区:与 LCS 一样取上/左;正解:连续要求断了即清零。
  • 误区:全局最大漏记。

追问

  • Q:LCS 区别? A:LCS 不连续,可继承上/左。
  • Q:滚动数组方向? A:倒序避免覆盖对角线。

02.9.1.4-016 数组第 K 大(LC 215)

一句话结论

最小堆维护 K 个最大元素,或快速选择分区缩窄;堆 O(n log K),快选平均 O(n)。

概念解释

考点:堆 / 快选;空间 O(K) / O(1)。

原理流程

  1. 堆:超 K 弹最小。
  2. 快选:分区定位第 K 位。

代码 / 示例

关联:堆排序与工程排序、去重布隆过滤器与 Top-K 堆

常见误区

  • 误区:全排序 O(n log n) 未优化。
  • 误区:第 K 大用最大堆口径混淆。

追问

  • Q:数据流 Top-K? A:固定最小堆持续维护。
  • Q:快选最坏? A:随机基准期望 O(n)。

02.9.1.4-017 合并 K 个升序链表(LC 23)

一句话结论

最小堆存各链表头节点,每次弹出最小接入结果,后继入堆;或分治两两合并。

概念解释

考点:堆 / 分治;时间 O(N log K),空间 O(K)。

原理流程

  1. 各头节点入堆。
  2. 弹最小接入,后继入堆。
  3. 堆空完成。

代码 / 示例

关联:优先队列堆与栈队列综合

常见误区

  • 误区:堆中存整表而非头节点。
  • 误区:后继为 null 仍入堆。

追问

  • Q:分治合并复杂度? A:O(N log K),两两归并。
  • Q:K=1 边界? A:直接返回该链表。

02.9.1.4-018 数据流中位数(LC 295)

一句话结论

对顶堆:大顶堆存下半段,小顶堆存上半段,维护两堆大小差 ≤1;中位数取堆顶或两顶平均。

概念解释

考点:对顶堆;插入 O(log n),取中位 O(1),空间 O(n)。

原理流程

  1. 按堆顶关系插入对应堆。
  2. 平衡两堆大小。
  3. 按堆大小取中位。

代码 / 示例

关联:优先队列堆与栈队列综合

常见误区

  • 误区:插入后不平衡堆大小导致中位数取错。
  • 误区:大小顶堆方向写反。

追问

  • Q:有序数组插入? A:O(n) 搬移,堆更优。
  • Q:中位数定义偶数口径? A:两堆顶平均。

02.9.1.4-019 滑动窗口最大值(LC 239)

一句话结论

单调双端队列存下标,队列内值递减;右移入队维护单调性,弹出越界队首,队首即窗口最大值。

概念解释

考点:单调队列;时间 O(n),空间 O(k)。

原理流程

  1. 队列入队前弹出更小尾元素。
  2. 队首越界弹出。
  3. 窗口形成后记队首值。

代码 / 示例

关联:队列双端队列与循环队列

常见误区

  • 误区:队列存值不存下标,无法判越界。
  • 误区:相等元素也弹出导致后续窗口丢值。

追问

  • Q:与单调栈区别? A:队列服务滑动窗口滑动淘汰,栈服务最近更大元素。
  • Q:复杂度为什么 O(n)? A:每元素入队出队各一次。

02.9.1.4-020 轮转数组(LC 189)

一句话结论

三次反转:整体反转 → 前 k 个反转 → 后 n-k 个反转;原地 O(1) 空间。

概念解释

考点:数组技巧;时间 O(n),空间 O(1)。

原理流程

  1. k 取模 n。
  2. 反转全数组。
  3. 分别反转前后段。

代码 / 示例

关联:数组原地操作与快慢双指针

常见误区

  • 误区:k 未取模 n,k>n 错误。
  • 误区:反转分段边界算错。

追问

  • Q:额外数组做法? A:新位 (i+k)%n 拷贝。
  • Q:旋转方向? A:右移 k 位,三段反转顺序固定。