对顶

"始终在序列中某个指定位置进行修改"的性质

对顶栈

Acwing-128.编辑器

使用两个栈，栈顶对顶，动态维护光标位置

对顶堆

Acwing-106-动态中位数

使用一个大根堆一个小根堆，堆顶对顶，动态维护中位数

货仓选址

货仓选址

Acwing-104.货仓选址

中位数问题

二维货仓选址

P1889 士兵站队

中位数问题，公式变形

石子合并

每次合并2个

Acwing-148.合并果子

二进制编码huffman树

每次(最多)合并K个

Acwing-149.荷马史诗

K进制编码huffman树

每次合并2个(加强版)

P6033 [NOIP2004 提高组] 合并果子 加强版

桶排序 + 队列

每次合并相邻2个(链式)

P5569 [SDOI2008] 石子合并

区间DP

每次合并相邻2个(环形)

P1880 [NOI1995] 石子合并

区间DP

每次合并连续K个(链式)

LeetCode-1000.合并石头的最低成本

区间DP

均分纸牌

链式均分纸牌

P1031 [NOIP2002 提高组] 均分纸牌

均分纸牌，最后一个人不传递

环形均分纸牌

P2512 [HAOI2008]糖果传递

考虑如何破环成链=>存在最优解，使得环中有相邻两人之间没有发生交换，以此作为断点.

约瑟夫环

P1996 约瑟夫问题

比较经典的做法就是用链表构造循环链表，或者用双向队列构造循环队列

超级源点

多源BFS

Acwing-173.矩阵距离

多源dijsktra

Acwing-1488.最短距离

差分约束

计算几何

平面最近点对

P1257.平面最近点对

P1429 平面最近点对（加强版）

P7883 平面最近点对（加强加强版）

给你一组points，要你求距离最短的两个point

分治

非常经典的计算几何问题，需要分治下标区间来做。

平面最小面积矩形

LeetCode-939.最小面积矩形

给你一组points，确定由这些点组成的矩形的最小面积，其中矩形的边平行于 x 轴和 y 轴。

枚举对角线上的两个点 + hash

先把所有点按hash值$(x * 40001 + y)$，存入hash表，由于题目数据，可以保证不发生冲突。
然后$O(n^2)$枚举对角线上两个点，再判断另外两个点是否在hash表中，由此判断能否组成矩形，即可计算答案。

平面上判断圆形和矩形相交

LeetCode-1401.圆和矩形是否有重叠

可用使用向量的形式，来统合所有分类讨论的情况，具体原理见知乎回答

子数组问题

子数组要求是在原数组中连续的一段

• DP，(一般都是线性)
• 前缀和+哈希表
• 滑动窗口，(可能会用到双端队列) => 这种一般是固定长度的子数组

最大子数组问题

最大子数组

剑指offer42.连续子数组最大和

Method1：DP

状态集合：$f[i]$ ： 表示以当前下标$i$ 结尾的所有子数组中的最大和。

转移方程：$f[i] = max(f[i - 1] + arr[i], arr[i])$

由于当前状态只与上一个有关，因此可以用滚动数组优化空间

Method2：预处理为前缀和问题， 找出两个下标l,r 使得,S[r] - S[l]最大，并且 r >= l，

这里再维护一个当前位置前缀和的最小值下标数组（作为l），然后枚举r，时间复杂度同样是O(n)

环形子数组最大和

长度为K的最大子数组

LeetCode-2461.长度为 K 子数组中的最大和

滑动窗口

对于每个滑动窗口, 我们可以使用 $O(k)$ 的时间遍历其中的每一个元素, 找出其中的最大值。 对于长度为 $n$ 的数组 nums 而言, 窗口的数量为 $n-k+1$, 因此该算法的时间复杂度为 $O((n-k+1) k)=O(n k)$, 会超出时间限制, 因此我们需要进行一些优化。

长度不超过K的最大子数组

Acwing-135.最大子序和

前缀和 + 单调队列优化DP

不固定长度，预处理为前缀和问题， 找出两个下标l,r 使得,S[r] - S[l]最大，并且 r - l >= M

最长子数组问题

和为0的最长子数组

面试题17.05.字母与数字

前缀和+哈希表

找到一个最长子数组，其元素和等于 0 => 用前缀和处理，「元素和等于0」等价于「两个前缀和之差等于 0」，进而等价于「两个前缀和相同」

从前缀和 s中找到两个相同的数 s[right]和 s[left]，并使得right−left 最大。
用hash表记录前缀和中每个数字第一次出现的下标，然后每当再次遇到该数字，计算当前的长度间隔，由此得到最大间隔。

前缀和+哈希表的用法真的很经典

其它子数组问题

统计和为K的子数组

LeetCode560.和为 K 的子数组

前缀和+哈希表

首先，和为k的子数组，一眼就可以转成前缀和,求$s[r] - s[l - 1] == k$。

那么可以转化成$s[r] - k == s[l - 1]$

那么遍历数组，每次计算到当前前缀和$s[i]$时，可以看看哈希表中$s[i] - k$的个数，然后直接加上就能统计出来。

特别地，哈希表要初始化{0，1}，可以看作是在前缀和前多加了一个和，是为了防止从序号0开始加到序号i时刚好为k的情况出现时，没法找到对应数值计数。

统计中位数为K的子数组

LeetCode-2488. 统计中位数为 K 的子数组

前缀和+哈希表

这道题有限制的：数组内的数字各不相同为1~n，并且规定偶数长度的子数组其中位数是位于中间靠 左 的元素

子数组的中位数如果是K，等价转换：预处理数组，把数组中小于K的数视作-1，大于K的数视作-1，K视作0。

• 对于奇数长度的子数组，「子数组中小于K的数的个数 == 大于 K 的数的个数」，等价于前缀和为k_

• 对于偶数长度的子数组，「子数组中小于K的数的个数 == 大于 K 的数的个数 - 1」，等价于前缀和为k_ + 1

由此可以转换成「统计和为K的子数组」这道题。

子序列问题

因为不要求连续，所以如果是统计子序列长度问题，

可以先排序看看，然后想想能不能二分查找

然后就是DP了