算法与数据结构

算法与数据结构

算法思路与模板

二分查找要求序列有序，每次将搜索范围缩减一半，时间复杂度 O(log n)。 两个指针从两端向中间收缩，常用于有序数组。 滑动窗口维护一个满足条件的区间 left, right，right 不断向右扩张，条件不满足时收缩 left。 滑动窗口通用框架： 1. 确定"子问题"：原问题可以分解为哪些规模更小的同类问题 2. 定义 dpi 或 dpij 的含义，要足够清晰 3. 推导状态转移方程 4. 确定初始状态（边界条件） 5. 确定计算顺序（确保依赖的子问题先计算） 每件物品最多选一次。dpj = 容量为 j 时的最大价值，逆序遍历容量防止重复选取。 每

算法与数据结构

数据结构完全参考

Python list 是动态数组（Dynamic Array）： 推论：需要频繁头部操作时，用 collections.deque 替代 list。 循环链表将尾节点的 next 指向头节点。常见于约瑟夫环问题。使用时注意遍历终止条件应以初始节点为准，否则会无限循环。 栈遵循 LIFO（后进先出）原则。 队列遵循 FIFO（先进先出）原则。 Python heapq 是最小堆。实现最大堆时将值取反。 单调栈维护一个单调递增或递减的栈，用于求"下一个更大/更小元素"。 单调队列用于滑动窗口最值问题，队列中元素单调递减（求最大值）或单调递增（求最小值）。