[toc]
梳理
解题思考
- 每个题的时间/空间复杂度是多少，及最好/最坏情况的时间/空间复杂度
算法框架
前缀和
解决的问题：
题目特点（如何辨析是否使用）：
经典题目：
差分数组
解决的问题：
题目特点（如何辨析是否使用）：
经典题目：
双指针
解决的问题：
题目特点（如何辨析是否使用）：
经典题目：
滑动窗口
解决的问题：
题目特点（如何辨析是否使用）：
经典题目：
二分查找
解决的问题：
- 查找某个数
- 确定左/右边界线
题目特点（如何辨析是否使用）：
经典题目：
⼒扣第 34 题「在排序数组中查找元素的第⼀个和最后⼀个位置」
力扣875. 爱吃⾹蕉的珂珂（中等）
力扣1011. 在D天内送达包裹的能⼒（中等）
田忌赛马
解决的问题：
题目特点（如何辨析是否使用）：
经典题目：
- 力扣870. 优势洗牌（中等）
链表操作递归秘籍
解决的问题：
- 翻转链表
- 部分翻转链表
题目特点（如何辨析是否使用）：
经典题目：
LeetCode 206. 反转链表（简单）
LeetCode 92. 反转链表 II（中等）
-——–
括号题目
解决的问题：
- 平衡括号串（一）p119
- 平衡括号串（二）p120
题目特点（如何辨析是否使用）：
经典题目：
- ⼒扣第 921 题「使括号有效的最少添加」
- ⼒扣第 1541 题「平衡括号字符串的最少插⼊次数」
单调栈
解决的问题：
- 后面第一个更大的数
思考：
- 为什么要用从后往前的方式入栈？
- 因为最后要输出的是更大的数的值，而不是索引，如果是从前往后入栈，入栈的元素就只能存入值，它的索引就丢了，而最终的结果是要按照这个索引把值替换掉，所以不能这么解
题目特点（如何辨析是否使用）：
经典题目：
LeetCode 上拿下如下题⽬：
\496. 下⼀个更⼤元素I（简单）
\503. 下⼀个更⼤元素II（中等）
\739. 每⽇温度（中等）
-———
单调队列
解决的问题：
- 滑动窗口
题目特点（如何辨析是否使用）：
经典题目：
- \239. 滑动窗⼝最⼤值（困难）
去重算法
解决的问题：
题目特点（如何辨析是否使用）：
经典题目：
LeetCode 上拿下如下题⽬：
\316. 去除重复字⺟（中等）
\1081. 不同字符的最⼩⼦序列（中等）
LRU
解决的问题：
题目特点（如何辨析是否使用）：
经典题目：
LFU
解决的问题：
题目特点（如何辨析是否使用）：
经典题目：
常数时间随机读取/删除数组元素（P153）
数据结构设计题
解决的问题：
题目特点（如何辨析是否使用）：
经典题目：
LeetCode：
\380. 常数时间插⼊、删除和获取随机元素（中等）
\710. ⿊名单中的随机数（困难）
如何在无限序列中随机抽取元素（P611）
解决的问题：
题目特点（如何辨析是否使用）：
经典题目：
去 LeetCode 上拿下如下题⽬：
\382. 链表随机节点（中等）
\398. 随机数索引（中等）
笔记框架
解决的问题：
题目特点（如何辨析是否使用）：
经典题目：