8月计划

分治

23：合并k个有序链表：

解法1：优先队列：注意不要把所有的节点全部加到优先队列里，因为每个链表本身都是有序的，所以初始化的时候只需要将链表的表头加入队列。之后每次弹出的时候再将弹出节点的下一个节点入队即可。
解法2：分治法-归并排序两两合并：注意不要使用普通的合并，太低级了，应该使用归并两两排序。

单调栈

84：柱状图中的最大矩形：这题和接雨水很类似，接雨水以height[i]为考量，找左右最大的值，通过普通遍历即可确定left[]和right[]数组，这题是以height[i]为考量，分别找出左右最近的比height[i]小的下标，关键词，最近，使用单调栈，关键词小，维护递增栈。

优化：左右数组都需要求出来的时候，正常情况下，需要求两次单调栈，但是我们可以再求左数组的时候，入栈i的时候，可以找出i的最左元素；其实我们在出栈i的时候，i的最右节点就已经确定，但是有些元素不会出栈，他们的默认值不是0，而是length，所以我们一开始可以对右数组全部初始化成length，length称为哨兵

85：二维数组的最大矩形：这题由84题升级而来，比84难的是84题一开始确定了高，需要求宽，这题宽高都未知。我们可以选取其中任意一条边，假设是高，那位新初始化一个heigh数组，heigh[i][j]表示以nums[i][j]为底的高，然后和84题一样左右单调栈求宽。
503：下一个更大温度II：普通的单调栈升级，可以利用循环数组取余初始化。

滑动窗口

滑动窗口用于解决最长/最短的子数组的问题，前提是需要明确窗口左移和右移的时机。例如leetcode1248虽然也可以使用滑动窗口解决，但不是求得最长/最短子数组，所以分析起来有点麻烦。

前缀和

用于求解某一段连续部分的和或者连续的部分包含的特性。可以使用前缀和+hashMap降低时间复杂度，注意hashMap初始有值，为（0，1）；

leetcode560
leetcode437: 虽然是树，但涉及到连续部分的和，可以用前缀和的方法，注意树和数组不一样，所以树的一个节点dfs完要将此节点的sum移出map
leetcode1248：虽然不是求和，但涉及到连续部分的特性，且不是最长/最短连续部分，用滑动窗口有点麻烦，所以采用前缀和的方式。

滑动窗口和前缀树

使用滑动窗口的不一定能用前缀树，使用前缀树的也不一定能用滑动窗口

前缀树本质就是枚举所有的 nums[i]-nums[j]的情况，不过可以用hahmap优化时间复杂度，例如leetcode560只能用前缀树

滑动窗口的重点在于知道什么该左移，什么时候该右移；例如最长无重复子串，只能用滑动窗口。

差分数组

差分数组用于需要在数组的某一段区域内全部加上或减去某个值的时候，比如要往num[i]-nums[j]+k; 我们可以让diff[i]+=k, diff[j]-=k。 **leetcode1094 **

两数相乘：位数k1 *位数 k2的位数最多是k1+k2；
使用数组来存储某一位的结果
第 i 位可能是两位数，放在nums[i]和nums[i+1]上，如果放在nums[i]和nums[i-1]上，第0位会溢出。
将乘积加上nums[i+1]形成的数，将个位放到nums[i+1],将其余位加到nums[i]。这样迭代，就能保证最终每一位上都是个位数。