最近2场LC周赛的最后一道，都运用了一些优化知识。四边形不等式优化和二进制优化，之前不久还有一场用到了单调队列优化。在这里对这5类优化做一个梳理。
分别是二进制优化，单调队列（栈）优化，斜率优化, 四边形不等式优化， 快速幂优化.
所谓优化
所谓优化，就是在原有算法的基础上提升时间/空间复杂度的方式。这些优化方式都是建立在能把基本的DP转移方程搞定，然后想如何提升效率。所以DP是基本功，这讲讲的都是一些进阶知识，针对DP有一定基础的同学。
二进制优化
这类问题一般是这样的，我们有一个数字K，我们需要枚举他的1~K 这里的所有可能。
比如经典的背包问题，有一个商品只剩7个了。我们如果把它当做01背包来处理，可以把这个商品看成，1个一种，2个合并拿为另一种，3个合并拿为第三种。。。一直到7个。当然7种可能里只能选1种可能，他们之间是互斥的，所以需要放到枚举体积的循环内。
这样子时间复杂度是 背包容量 * 物品种类 * 物品个数。
我们来看下代码
public static int backpack(int[] wei, int[] val, int[] cnt, int W) {
int n = wei.length;
int[] dp = new int[W + 1];
for (int i = 0; i < n; i++) { // 枚举物品种类
int curWei = wei[i], curVal = val[i];
for (int j = W; j >= 0; j--) { // 枚举体积
for (int k = 1; k <= cnt[i]; k++) { // 枚举此种物品个数
if (k * curWei > j) break;
dp[j] = Math.max(dp[j], dp[j - k * curWei] + k * curVal);
}
}
}
return dp[W];
}
下面就引入了2进制优化的思考，7在二进制表示下是111. 那么我们其实可以用100,010,001.进行组合而表示出所有7种可能性。比如这3个数字全不选是000， 选第一和第三个就能组合出101.
所以我们其实可以不用枚举所有的7种可能性，我们只要组合出3种可能性就好。 这里的3其实是7的LOG。
所以时间复杂度 那一维的时间复杂度可以优化到LOG N。
在继续深入下去之前，我们可以先看一道这个思想的题热个身。
https://leetcode.com/problems/patching-array/
这道题就差不多是类似的思想，我需要加进去哪些数，就可以组合出所有的1~N的数。这题就是判最小的那个未满足的数是几，把它引入。然后找下一个未满足的。如果下一个满足，就把这个范围拉大。比如[1,3,10] 要组合出11以内的数。先看1有没有，有了加进来，sum=1。发现2没有，所以要补2. sum=3. 3 < sum ，加进来。 sum = 6. 然后就会发现7没有，要补7。依次类推。
而我们这里的思想是把一个数拆成尽可能少的数，使得他们的组合出来的全集是1~这个数的集合。
这里和之前不一样的地方是组合。也就是说我们之前把7种物品是看成互斥的（选了里面1个，就不能再选另外6个），而现在我们可以把这3种物品看成不互斥的（为了让他们能组合起来，选了一个还有机会选另一个）
所以我们要把这层循环放到W之前。其实暗示的含义是这样我们把7个的A物品，变成了B物品（001），C物品（010），D物品（100）。每种都可以选1次或选0次。
如果总数是8个， 我们需要一个B物品(001), C物品(010), D物品(100),但是这样我们只能表示所有0-7的可能，而此时无法引入（1000），因为并没有15 个物品这么多。所以最后一个（8-7=001）为E物品
下面是代码
public static int backpack(int[] wei, int[] val, int[] cnt, int W) {
int n = wei.length;
int[] dp = new int[W + 1];
for (int i = 0; i < n; i++) { // 枚举物品种类
int curWei = wei[i], curVal = val[i], restCnt = cnt[i];
for (int k = 1; restCnt > 0; k <<= 1) { // 枚举此种物品个数
if (k > restCnt) k = restCnt;
restCnt -= k;
for (int j = W; j >= k * curWei; j--) { // 枚举体积
dp[j] = Math.max(dp[j], dp[j - k * curWei] + k * curVal);
}
}
}
return dp[W];
}
下面我们来看另一个问题，这里会讲2个优化
https://leetcode.com/problems/sliding-window-maximum/
这道题是非常经典，就是求滑动窗口的最大值。我们知道求滑动窗口的，一般维护2个指针就好。然后左指针和右指针移动的时候看怎么更新状态。比如求窗口中位数。我们维护2个堆，一个大根堆存小的一半的数。一个小根堆存大的一半的数。左右指针滑的时候，我们可以知道这个数应该要从哪个堆移除，和加入。
而最大值稍微复杂一些，如果我们只是维护一个目前的最大值，如果新加进来的数比最大值大则更新。但是新离开的数和最大值一样的话就麻烦了。我们没有维护第二个大的值。即使多维护一个第二大的变量，当他成为最大值并离开时，我们又麻烦了。那其实是要维护窗口内的所有数了。
这个时候，我们要思考的点是一个数什么时候是无用数，无用数就是他的存在没有任何可能去改变结果。比如【9,8,7,6】这里没有无用数，因为虽然一开始是9是老大，但是窗口右移，之后每个数都有机会去做老大。我们再看一组数[1,2,3,4]. 如果是求最大值，那么前3个是彻底没用的，如果窗口是4的话，因为4的存在他们是绝对不会成为任何一个窗口的最大值。
这里其实引入了数据特权的2个维度。这和打德州扑克很像，即使你牌不够大，如果你的位置有优势，总体优势不一定只看牌的大小。而这里的数据其实也是这2个维度，一个是位置，一个是大小。只有当2维都落后时，这时才是无用数。
我们来重新定义一下无用数。就是位置和大小都比当前窗口的某一个数要差，那么就可以直接丢弃这个数。这个背后的思想也就是单调栈和单调队列优化的思想。
我们在进栈的时候，可以去看，前面的数一般算位置比自己差的，因为我是后进栈（后浪之后还有无限可能）如果前浪除了剩余时间少，另一个维度也输给了后浪，前浪就可以出栈了。
按照这个思想，因为我们要的是最大值，我们后浪来的时候，如果是最大的，其实是可以把所有前浪都弹出去，直到遇到一个更大的前浪，他就安静的待在他后面，直到时间流逝（窗口滑动），前浪自然离开，这个后浪就登上了历史舞台，前提是没有更后浪把他带走。
这样看单调栈的思想其实还蕴含着一定的社会规律。
基于上述思想，队列头部就是最大的数了。每次滑动的时候，需要看看，这个数的寿命是不是到了。如果到了就把他从队头弹出，那么之后就是第二大的了。当一个数新进来时，就看看有没有混得比自己差的前浪，让他们从队尾弹出。
所以单调队列的本质是一群年龄从老到小的数据，维持了本事从高到底的排序这就是单调的来由
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums.length == 0 || k == 0) return new int[0];
Deque<Integer> dq = new ArrayDeque<>(nums.length);
int[] res = new int[nums.length - k + 1];
int idx = 0;
for (int i = 0; i < nums.length; i++) {
if (i >= k && nums[i - k] == dq.peekFirst())
dq.pollFirst(); // 前浪自然死亡
while (!dq.isEmpty() && nums[i] > dq.peekLast()) {
dq.pollLast(); // 后浪淘汰前浪
}
dq.offerLast(nums[i]); // 后浪入队等待机会
if (i >= k - 1)
res[idx++] = dq.peekFirst(); // 后浪登上历史舞台
}
return res;
}
在深入一些
我们之前讲到了数据的2个维度。并结合这个来思考如何让后浪淘汰前浪，而引出了单调队列和单调栈。下面又是一个很经典的问题，叫最长（最短）子数组的和满足XXX条件。
比如https://leetcode.com/problems/minimum-size-subarray-sum/
这道题。
要求的是最短的子数组和要>=S。题目说明数组里全是正数。这是一个经典的可变长度的滑动窗口，窗口为了要尽可能的小，所以一旦满足条件，左侧就开始收缩，直到不再满足条件为止。更新MIN SIZE。然后继续移动右侧使得满足条件。
这种算法其实和做企业很像，右指针是不断去开拓新的可能，找到了盈利模式后。移动左指针，不断去压缩成本，保持自己的竞争优势。
当然上面的假设很美好，因为所有的数据都是正数的，所以我们可以保证的是，我们的每一次努力，都是正反馈（不可能移动了左指针，成本反而比之前高）
但是现实并不一定这么美好，因为有很多未知数。可能辛苦付出的研发投入，最后被证明是毫无价值的。那么在含有负数的时候应该怎么考虑这类问题呢？
其实这也对应了一道LEETCODE 题目，这题就变成了HARD了。生活其实就都是HARD这样的。
https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/
如果引入了负数，我们其实就没有了滑动窗口永远是正反馈的性质，那么窗口的不变量就变成了变量。这个时候比较容易想到的是构建前缀和数组，然和暴力枚举所有窗口的可能，用前缀和相减O(1)得到是否满足条件，并更新最短。这样窗口的窗口可能是O(N^2)的复杂度。
只能这样了吗？
在现实中我们遇到这样一个问题该如何破局呢？
如果是我，我会先尽一切可能找到一个可以满足要求的方案，然后再想怎么去优化。
那么我就先忘记最短这个条件，因为无论多短，都要先满足>=k.
那么我就从PRESUM 里去找，当我站在这个PRESUM时，我希望做的是之前有没有一个PRESUM 可以使得我们相减能满足条件。如果有，那么我再想优化，他是否是离我距离最短。
讲到这里你是不是发现了什么？对的，距离。又是你，出现了。前浪和后浪。
这里就像是找能一起完成任务的伙伴，如果有多个，我要选同龄人（共同话题多，代沟少，何乐为不为）
那么无用数也就很明显了。因为这里是要减去一个之前的PRESUM。为了使得我能完成任务（>= K）的概率尽可能高就意味着减去的数越小越好。（更有机会使得结果更大，更大就意味着更多可能>=K）
那么首先要保证任务完成，所以数值更小的PRESUM不能丢。其次是完成任务前提下，我希望数组长度越短。那么如果一个数又大又远，就是无用数了。
单调队列的本质是一群年龄从老到小的数据，维持了本事从高到底的排序
这里的本事是PRESUM 小，所以单调队列里队头是最小值。
我们当前这个PRESUM如果能和队头碰出火花了，其实队头的使命就结束了。因为他没必要再和我之后更年轻的人组队，因为代沟只会更大。而我，会不断弹出队头，直到一个人和我完成不了任务。那么我就知道和谁做任务代沟最小了。因为队列里的本事是单调递减的（队头完不成，之后的人虽然年轻但也还是完不成的）
说到这里我想你应该直到怎么做这题了吧。
public int shortestSubarray(int[] A, int K) {
int l = A.length, res = l + 1;
int[] presum = new int[l + 1];
for (int i = 1; i <= l; i++) {
presum[i] = presum[i - 1] + A[i - 1];
}
Deque<Integer> inc = new ArrayDeque<>();
for (int i = 0; i <= l; i++) {
// 优先确保有解，因为前端是最小的，先试最小的>=K 的概率最大
while (!inc.isEmpty() && presum[i] - presum[inc.peekFirst()] >= K) {
res = Math.min(res, i - inc.pollFirst());
}
// 保持单调性
while (!inc.isEmpty() && presum[i] <= presum[inc.peekLast()]) {
inc.pollLast();
}
inc.offerLast(i);
}
return res == l + 1 ? -1 : res;
}
现在我们再来看看要是目标是要求SUM <= K 该怎么做呢？
其实这就是数据的本事换了定义，之前我们认为，数值越小的越有本事。是因为减去小的，我可以有更大的概率满足>=K的条件。现在就是反过来了。为了让相减之后，尽可能小。那么数值大的被认为是本事大。所以只要把单调递增队列 变成递减即可。
下面给大家留一道思考题，如果是求最长的SUBARRAY 要求SUM >= K 或 <= K 该怎么做呢？
回到滑动窗口最大值
上面我们已经讲了单调队列的算法是怎么一回事。下面我们再来看看这道题的另一个做法。
因为窗口大小是固定的，我们在任一段落决定的他的值是有限的数据。假设我们把所有数据全划分为窗口大小的片段。然后对这个片段求出最大值。那么只要解决跨片段的问题就能把问题解决，一般也只需要考虑2个片段的数据，就可以得出跨片段窗口的最大值了。
下面就是思考如何用O（1）的时间去处理2边片段的数据，得到跨片段的最大值呢？
image.png
不难发现我们只要知道左片段右半部分的最大值，和右片段左半部分的最大值就可以算出窗口的最大值。
按照这个思路。我们需要维护2个DP数组，分别存储每个片段的左半部分的最大值和右半部分的最大值。 然后指针滑动的时候取MAX就可以O(1)时间轻松拿到解。
public int[] maxSlidingWindow(int[] nums, int k) {
int l = nums.length;
if (l * k == 0) return new int[0];
int[] left = new int[l]; // 右片段的左半部分的最大值
int[] right = new int[l]; // 左片段的右半部分的最大值
for (int i = 0; i < l; i++) {
if (i % k == 0) left[i] = nums[i];
else left[i] = Math.max(left[i - 1], nums[i]);
int j = l - 1 - i;
if ((j + 1) % k == 0 || j == l - 1) right[j] = nums[j];
else right[j] = Math.max(right[j + 1], nums[j]);
}
int[] res = new int[l - k + 1];
for (int i = 0; i < res.length; i++)
res[i] = Math.max(right[i], left[i + k - 1]);
return res;
}
上面的思路也是非常经典。我们下面想想这个问题的更一般形式。一个数组，我们如何在O(1)时间求出任意窗口的最大值呢。
继承上面的思路，我们知道如何用窗口大小的K 来在O(1)时间找出任意窗口为K的最大值。那么我们在预处理的时候，只要把K从1枚举到N就可以了。然后查找就是O(1)的了。
其实这个思路一点没有毛病，因为在这种做法下，等价于把所有要查询的可能给CACHE住了。其实我们可以先想下有了K值的LEFT数组和RIGHT数组，可以用O(2)的时间解决2 * K的窗口吗？
这个应该非常好想。把2个K的窗口的最大值求出来然后对这2个最大值给取MAX。
那K~ 2 * K - 1的窗口该如何求最大值呢？
其实用K值的LEFT和RIGHT数组也是可以求的， 只不过这个时候2个窗口中间会有重叠的部分，不过对取MAX没有任何影响。
如下图，K=3， 求窗口为4（红色）的最大值。可以用这样2个K=3的窗口（绿色和蓝色）最大值给求解出来。
image.png
这种做法再处理2 * K 以上的窗口，随着窗口越来越大，性能会越来越慢。所以我们就需要引入更大一些的K。这样在处理大窗口的时候就用大K，小窗口用小K。这个跟做测量是一样的，你要测量一直铅笔需要一把直尺就好了。要是要测量头发丝就需要螺旋测微器。
那么我们需要思考的就是如何构建出一套最精简的工具包使得，任意窗口K都可以有对应的工具，立刻量出。
这又回到了我们的2进制思想。比如窗口大小的二进制为(101101)，我们只需要用最高位是1，剩余位全0(10000)的工具就一定可以覆盖住它.
32的工具 可以覆盖掉32-63的所有最大值计算，原理如上图左右2边分别计算出2个32的最大值，取最大
那么这样我们最多只要构建31组工具，就可以实现所有窗口的O(1)测量了。
同样是刚才那道题，我们可以直接丢工具包进去做。二进制本质上是LOG(N)的复杂度，所以构建工具包的时间复杂度O(N LOG N)
这里构建工具包有一些技巧，我们可以用低长度的工具包，O(1)时间构建出高一层长度的工具包。
int[][] rangeMaxQuery(int[] nums) {
int l = nums.length;
int[][] dp = new int[l][20]; //dp[i][j] = 从i 开始，长度为2^j 的窗口里最大值是多少
for (int i = 0; i < l; i++) dp[i][0] = nums[i];
for (int j = 1; (1 << j) <= l; j++) {
for (int i = 0; i+(1 << (j-1)) < l; i++) {
// dp[0][1] = max(dp[0][0], dp[1][0]) 低长度工具包构建高长度工具包
// dp[0][2] = max(dp[0][1], dp[2][1]) ...
dp[i][j] = Math.max(dp[i][j-1], dp[i+(1 << (j-1))][j-1]);
}
}
return dp;
}
有了上面这个工具包，我们再求窗口最大值时只需
res[i] = Math.max(dp[i][num], dp[i + k - (1 << num)][num]);
num为最高位1是第几位（0开始计数）
二进制优化++
再回到今天的周赛题来,https://leetcode.com/problems/kth-ancestor-of-a-tree-node
题目给了一颗有根树，要求任意节点的第K个祖先，如没有返回-1. 暴力解就是从这个节点向上走K步，然后输出第K个祖先。可是题目的树深可能达到50000，并且有50000次查询，所以这样做很有可能会超时。
比如我们要找第15个祖先，有没有什么快速的方式呢？我们可以用二进制的思想。15的最高位1为8.那么我是否可以先跳8步，看那个祖先是谁，然后基于那个祖先再找他的第7个祖先即可。这样子只需要LOG N的时间，就可以定位了。
那么我们也是要构造和前面一个情况一样的工具包。这个工具包里需要摆放的是每一个节点，往后1步，2步，4步，。。。2^k步的父亲节点是谁，如果跳过根节点存-1.
我们也是和上面一样的构造工具包的思路，先构造一步的，随后用1步的去构造2步的。
int[][] dp;
public TreeAncestor(int n, int[] parent) {
int highestOneTrailingZero = Integer.numberOfTrailingZeros(Integer.highestOneBit(n));
dp = new int[highestOneTrailingZero + 1][n];
dp[0] = parent;
for (int i = 1; i < dp.length; i++) {
for (int j = 0; j < n; j++) {
int par = dp[i - 1][j]; // 用0的J 来构建 1的J
dp[i][j] = (par == -1 ? -1 : dp[i - 1][par]);
}
}
}
然后来找的时候，比如找15，我们先要去跳8下的祖先，然后去找该祖先的跳7下（这里再用最高位来2进制跳）一直跳到-1，或第15个祖先退出循环。
public int getKthAncestor(int node, int k) {
while (k > 0 && node != -1) {
int i = Integer.highestOneBit(k);
int par = dp[Integer.numberOfTrailingZeros(i)][node];
node = par;
k -= i;
}
return node;
}
上述就是二进制思路的基本思想。本质是一个数字，可以转换到2进制，然后依次处理二进制的每个1，而达到快速攻克某个问题的效果。
构造工具包的时候，一般从最底层的1，依次往上构造。
看到这里再回想一下，我们已经讲述的2进制优化的3个问题，分别是多重背包的二进制优化，区间最大值的二进制优化，和第K个祖先的二进制优化。
单调队列优化
下面我们来看第二种DP优化方式，单调队列。之前已经讲过了单调队列是怎么一回事。他的核心就是一群年龄从老到小的数据，维持了本事从高到底的排序。 新数据进来时需要淘汰无用数。
在一类DP问题中，我们可以用单调队列的思想来进行降维打击。我们来看我上次周赛遇到的一道题。
https://leetcode.com/problems/constrained-subsequence-sum/
这道题的意思是我们要构造一个子序列（顺序要保证，中间可以跳元素）这个子序列中间跳的元素不能超过K。也就是K=2，只能跳1个元素。K=1，子序列的数之间必须相邻。
那么很快就可以想到的是根据数组长度来构建DP，DP I，来表示数组的前I项，且最后一项选中的最大值。那么最后一项选。前面K个数是可以有2个情况，选或不选。
所以转移公式为
dp[i] = (max{j from [i - k, i)} dp[j]) + cur[i]
这里我们可以看到每一个DP需要从前面K个状态转移过来，那么时间复杂度就为O (N * K）
你看到这里会发现其实那个MAX的变量是在根据I 指针在滑动的而且是定长的。那么其实直接套上之前的滑动窗口最大值的维护，就可以把这里O(K)的枚举 变成O(1)的取窗口最大了。
下面是我用，数组来模拟双端队列的比赛时写的一段代码
public int constrainedSubsetSum(int[] nums, int k) {
int ans = Integer.MIN_VALUE, l = nums.length;
int[] q = new int[l+1];
int hh = 0, tt = 0;
int[] dp = new int[l + 1];
for (int i = 1; i <= l; i++) {
if (hh <= tt && i - q[hh] > k) hh++; // 非空，且寿命到了，前浪退出历史舞台
int cur = nums[i - 1];
dp[i] = Math.max(cur, dp[q[hh]] + cur);
ans = Math.max(ans, dp[i]);
while (hh <= tt && dp[i] >= dp[q[tt]]) tt--; // 后浪淘汰本事不行的前浪
q[++tt] = i;
}
return ans;
}
这道题还可以有一个变形，之前我们的限制是空挡不能大于等于K。现在我们的要求是选出子序列，连续的数不能大于等于K，这里我们限制数组里的数都为正数，又应该怎么做呢？
之前我们为了限制空挡，要求最后一个数必须拿。这样我们就可以通过枚举前K个必拿的状态转移到目前MAX的不会有K空挡的状态。
而现在为了不能持久连续，我们依赖用前K个状态，此时已经不要求最后一个必拿，只要结果最大即可。破坏连续K个的核心就是枚举，这个不拿是K个里的什么位置。
可是自己这个不拿，然后就是DP[I-1]，也可以是DP[I-2] + ARR[I]，也可以是DP[I-3] + ARR[I] + ARR[I - 1]。。。这里我们发现了一个数组求和，我们可以用PRESUM，来把这个求和的步骤变成O(1)
转移公式为
dp[i] = (max{j from [i - k, i)} dp[j - 1] - presum[j]) + presum[i]
这里的意思我们确定J 不拿了，J之前的用DP[J-1]取到最大，之后的用PRESUM求出来（因为数都是正数可以贪心只丢一个）
而单调队列里存的就是之前K SIZE WINDOW的 (dp[j-1] - presum[j]) 的最大值。
依旧是区间窗口最大值的维护。
主代码如下
int[] dp = new int[n + 1]; // DP 从 1 到 N
int h = 0, t = 0;
for (int i = 1; i <= n; i++) {
if (h <= t && i - q[h] > k) h++;
dp[i] = max(dp[i - 1], presum[i] + help(q[h]));
while (h <= t && help(i) >= help(q[t])) t--;
q[++t] = i;
}
return dp[n];
HELP函数如下
int help(int i) {
if (i == 0) return 0;
return dp[i - 1] - presum[i];
}
总结
今天讲述了DP优化中的两类，分别是二进制优化和单调队列优化。我们不妨回顾一下，二进制优化是把对数的遍历拆成对每一个二进制1的遍历而提升效率。效率提升幅度为O(N)->O(LOG N)。而单调队列的优化通常就是维护区间最值属性直接获得最佳状态减少一层状态转移的遍历而提升效率。效率提升幅度为(O(K) -> O(1))
下一讲会带大家一起进入神奇的四边形不等式优化和斜率优化和快速幂优化。看数学是怎么帮助我们提升代码性能的。
最后给大家留一道二进制优化的思考题和单调队列优化的思考题。
在一棵有根多叉树中，如何使用二进制优化，来找最近公共祖先呢？
总共有 n 道题目要抄，编号 0,2,…,n，抄第 i 题要花 ai 分钟。老师要求最多可以连续空的题为K，求消耗时间最少满足老师要求的方案。
网友评论