数组&排序
88、合并两个有序数组
1
2
3
4
5
| + 双指针 + 倒排
+ while循环（条件：下面退出）
+ 上指针未结束，且大于下指针
+ 上指针结束（提前走完）或者小于下面指针
+ 其他方法
|
75、颜色分类
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| + 对数组排序（只包含0、1、2），原地排序（常数空间），一趟扫描
+ sort ×
+ 排序算法 ×
+ 双、三指针（扫描一趟常用解法）
+ 左边两个指针（放0、遍历扫描），右边一个指针（放2），判断左边元素
+ 遍历（条件：扫描退出）
+ 扫描到1跳过
+ 扫描移动
+ 扫描到0与左指针交换
+ 左指针移动
+ 扫描移动（交换来的值已经被扫描过，无需判断）
+ 扫描到2与右指针交换
+ 右指针移动
+ 扫描再次判断（交换来的值未被判断过）
|
16、部分排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| + 找到中间未排序的区间（两边已排序）
+ 寻找逆序对
+ 找到最后一个逆序对
+ 花时间思考值得
+ 类似的问题就容易解决了
+ 总结、思考
+ 双指针
+ 两边同时扫描
+ 记录扫描过程的最大值
+ 若比最大值小，则记录位置（逆序）
+ 统计最大逆序位置
+ 记录最左和最右的最大逆序位置
|
练习
977、164-hard
总结
双指针（常用）
左右扫描
链表
203、移除链表元素
1
2
3
4
5
6
7
8
9
10
11
| + 删除节点
+ 想象成一个全新的链表
+ 如果是要删除的，跳过
+ 如果不是，连接节点
+ 双指针 + 遍历一遍
+ 一指针遍历，一指针指向尾节点
+ 若为删除节点，尾节点不动（非尾部）
+ 若为正常节点，尾节点指向当前
+ 虚拟头结点
+ 方便删除第一个节点
+ 遍历将next作为头
|
2、两数相加
160、相交链表
1
2
3
4
5
6
7
8
9
10
| + 快慢指针？
+ 拼接链表
+ 方法
+ 下一个为null时移动到另一个头结点
+ 原理
+ 两个链表长度相同
+ 最后的节点必然相同——相交之处（开始相同的地方）
+ 遍历（相同时结束）
+ 走完时到另一个节点头部
+ 结束时指向第一个相同位置
|
86、分隔链表
1
2
3
4
5
6
7
8
9
10
| + 两个虚拟头结点lhead、rhead
+ lhead
+ 小于的串进来
+ ltai指向末尾
+ rhead
+ 大于的串进来
+ rtail指向末尾
+ 配合last指针记录每条链表尾部
+ 遍历链表head指针
+ 判断值进行链表串接
|
234、回文联表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| + 1、链表反转
+ 1、创建新链表翻转
+ 2、后半部分原地翻转
+ 两个链表头
+ 双指针比较
+ 移动到null结束
+ 实现
+ 找到中间节点（常用操作）
+ 奇数-中间的
+ 偶数-左边的
+ 快慢指针
+ 快指针一次两步，慢指针一次一步
+ 快指针到头，慢指针到中间节点
+ 翻转链表（常用操作）
+ 指针逆序
+ 双指针遍历比较
+ 若需不改变原结构
+ 再次翻转
+ 这些基本操作100%快速手写
|
练习
138、708、237、141、206、21、23
总结
1
2
3
4
5
6
7
| + 99%题目画图
+ 虚拟头结点
+ 快慢指针
+ 求中心节点
+ 判断环
+ 多指针
+ 链表翻转
|
栈&队列
概念
1
2
3
4
5
6
7
8
9
10
11
| + 栈
+ 解决问题：对称
+ 回文链表
+ 前面半部分入栈
+ 后面半部分出栈判断是否相等
+ 有效的括号
+ 左右括号对称
+ 队列
+ 解决问题：顺序
+ 双端队列
+ 头尾都可添加、删除元素
|
155、最小栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| + 获取栈中最小元素
+ 要求常数时间
+ 空间换时间
+ 1、两个栈
+ 正常栈、最小栈（只存放当前及以下层最小数据）
+ 两个栈同步 入栈、出栈
+ 最小栈入栈只放最小值
+ 核心思想
+ push的时候知道当前栈的最小值
+ 维护一个最小值
+ 优化
+ 链表
+ head节点始终保存最小值
+ 头插法
+ 实现
+ 创建node类
+ 保存当前值和最小值
+ 初始化创建虚拟头结点
+ 值为最大
+ push
+ 维护当前值和最小值（比较head）
|
239、滑动窗口最大值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| + 为什么想不到方法？
+ 做的题太少！！！
+ 刷题
+ 套路总结
+ 1:暴力
+ 遍历，每次往后找k个元素
+ 2:动态规划
+ 3:双端队列
+ 准备
+ i指向滑动窗口最后一个元素
+ w指向第一个元素
+ node
+ 索引和对应的值
+ 实现
+ 从队尾入队，前面小的都移除
+ 队列中头元素最大
+ 当w合法时，获取队列头元素（滑动窗口最大值）
+ 移动后，判断队列头部元素索引是否有效
+ 队列按索引、从大到小排列
+ 只需遍历一遍O(n)
+ 原理
+ 索引判断节点位置，是否在滑动窗口
+ 值进行大小比较，前面永远是滑动窗口最大值
+ 思考每一步都是为了什么？
+ 为什么这么做
+ 必须要弄明白原理
+ 双端队列（linkedlist双向链表）
+ 遍历数组
+ while判断队头元素和当前元素
+ 删除全部比当前元素小的
+ 将i加入队尾
+ 检查窗口的索引是否合法
+ 最后k-1个元素结束遍历
+ 检查队头索引是否合法
+ 不合法移除
+ 最多只需删掉一个（每次移动都会删除）
+ 设置窗口的最大值
+ 队头元素设置到最大值数组中
+ 为什么使用双端队列？
+ 单调队列
+ 递减
+ 整体目的
+ 一次遍历找到滑动窗口最值
+ 找到最值：保证对头元素是当前滑动窗口的最大值
+ 大的元素往前靠
+ 小的元素没有意义
+ 队列单调
+ 4:双指针
+ 实现
+ 先扫描前k个元素找到最值的索引
+ 遍历数组
+ 每次移动，维护最大值索引
+ 若最值索引在滑动窗口内
+ 若最后元素大于最大值索引，设为最值
+ 若最后元素不大于，继续
+ 若不在窗口内，则重新扫描k个窗口元素，找到最值，更新最大值索引
+ 设置最大值索引为窗口最值
+ 性能
+ 对于递减数列，需要不断重新扫描最值
|
654、最大二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| + 先找最值
+ 左边元素：左子树构建最大二叉树
+ 右边元素：右子树构件最大二叉树
+ 递归
+ 找到指定范围中的根节点（最大值node）
+ 结束条件：范围左右重合，直接返回
+ 创建节点
+ 遍历扫描
+ 找到最值的索引i
+ 左子树递归找到根节点（left，i）
+ 右子树递归找到根节点（i，right）
+ 变种题目
+ 返回父节点索引数组
+ 每个元素，两边找（都有可能）
+ 往右找第一个比当前元素大的为父节点
+ 当前为左子树
+ 往左找第一个比当前元素大的为父节点
+ 当前为右子树
+ 取小的那个父节点
+ 大的是上层的
+ 单调栈
+ 暴力，每个位置扫两遍
+ 栈，扫描一遍
+ 用栈求左、右边第一个比它大的数
+ 实现
+ 栈从下往上，维护单调递减
+ 扫描元素
+ 判断栈顶元素是否大于当前
+ 小于栈顶，入栈
+ 栈顶元素为当前元素的左边第一个比它大的数
+ 大于栈顶，弹出栈顶元素
+ 当前元素设置为栈顶元素的右边第一个比它大的数
+ 小的元素全部出栈
+ 保证大的入栈
+ 原理
+ 能push进去，下面的元素比它大
+ 能pop出去，即将push的元素比它大
+ 反过来求？
+ 左小，右小
+ 实现
+ 准备
+ 栈、两个数组（左大右大）
+ 扫描元素，维护两个数组
+ 栈顶小，循环弹出
+ 设置栈顶右大为当前元素
+ 栈顶大，入栈
+ 设置栈顶为当前元素左大
+ 若栈顶为空，不设置
+ 设置父节点索引
+ 比较两个数组，找出最小的作为父节点
+ 两个for循环跟一个一样
+ 执行的东西一样
|
739、每日温度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| + 找到下次升温天数（和右大索引距离）
+ 直接复制过来，单调栈
+ 只记录右大
+ 设置结果为 右大索引-当前索引
+ 倒推法
+ 思路
+ 从右往左遍历元素
+ 类似动态规划
+ 如果j>i的值
+ j是右大
+ 如果j<i的值
+ 寻找j的右大继续判断
+ 找到j的右大作为新值
+ 找到j对应升温的天数
+ 如果仍然小，则继续移动，重新进入判断
+ 若找不到，则设为0
+ 如果j=i的值
+ 同样寻找j的右大
+ 实现
+ 倒序遍历数组
+ 循环（true）：必然会结束
+ 如果j比当前元素大的
+ j设为当前元素右大
+ 结束循环
+ 如果不存在右大
+ 设为0
+ 结束循环
+ 如果j与当前元素相等
+ 找到j的右大就是当前元素的右大
+ 结束循环
+ 如果j小于当前元素
+ j的右大作为新j
+ 继续循环
+ 原理
+ 动态规划的思想
+ 从后往前推
+ 前面的值依靠后面的值进行计算
+ 代码简化
+ 等于情况和小于情况合并
+ 等于也要找后面的元素，小于也要找后面的元素
|
练习
42接雨水、232…
总结
1
2
3
4
| + 单调栈
+ 求左大右大
+ 双端队列、单调队列
+ 滑动窗口最值
|
