如何选择滑动窗口、二分、动态规划算法
刷leetcode时对于一些最优/极值问题往往不知采用哪一种算法,故借助大模型学习一些算法要点。
1. 滑动窗口(Sliding Window)
特点
- 适用于 数组 / 字符串 的 连续子区间 问题。
- 目标通常是:区间内的最大/最小和、最长/最短长度、是否满足条件。
- 要求窗口左右移动时能 快速更新答案(O(1) 或 O(log n) 更新)。
常见题型
- 固定长度子数组的最大/最小和。
- 至多 / 至少 K 个不同元素的子串问题。
- 满足某个和 / 约束的最短或最长子数组。
关键词
连续子数组 / 子串 + 统计 / 优化
2. 二分(Binary Search / Parametric Search)
特点
- 答案具有 单调性:
如果某个值x
可行,那么 >x 或 <x 的区间整体也一定可行。 - 通过 判定函数 check(mid) 来决定搜索方向。
- 时间复杂度通常是
O(log n * f(n))
。
常见题型
- 最小化最大值 / 最大化最小值。
- 分割问题(切木头、运货、分糖果)。
- 阈值判定类问题(满足条件的最小时间 / 最大容量)。
关键词
最小化最大 / 最大化最小 + 判定函数单调
3. 动态规划(Dynamic Programming, DP)
特点
- 状态之间有 重叠子问题 和 最优子结构。
- 问题不能仅靠窗口滑动或单调性解决,需要逐步递推。
- 常见于 序列问题 / 组合问题 / 路径问题。
常见题型
- 背包问题(01 背包、多重背包、完全背包)。
- 最长子序列 / 编辑距离。
- 区间 DP、树形 DP。
- 棋盘/图上的最短路径或最大得分路径。
关键词
子问题重叠 + 递推关系明确
4. 贪心、搜索等算法待补充...
5. 快速判断流程
flowchart TDA[遇到最优问题] --> B{是否涉及连续子数组/子串?}B -->|是| C[考虑 滑动窗口 / 双指针 / 前缀和]B -->|否| D{答案是否具有单调性?}D -->|是| E[考虑 二分 + check 函数]D -->|否| F{问题是否有重叠子问题和最优子结构?}F -->|是| G[考虑 动态规划]F -->|否| H[尝试其他算法: 贪心 / 图论 / 搜索等]