最近2場(chǎng)LC周賽的最后一道，都運(yùn)用了一些優(yōu)化知識(shí)按灶。四邊形不等式優(yōu)化和二進(jìn)制優(yōu)化，之前不久還有一場(chǎng)用到了單調(diào)隊(duì)列優(yōu)化筐咧。在這里對(duì)這5類優(yōu)化做一個(gè)梳理鸯旁。
分別是二進(jìn)制優(yōu)化，單調(diào)隊(duì)列（棧）優(yōu)化量蕊，斜率優(yōu)化, 四邊形不等式優(yōu)化铺罢， 快速冪優(yōu)化.

所謂優(yōu)化

所謂優(yōu)化，就是在原有算法的基礎(chǔ)上提升時(shí)間/空間復(fù)雜度的方式残炮。這些優(yōu)化方式都是建立在能把基本的DP轉(zhuǎn)移方程搞定韭赘，然后想如何提升效率。所以DP是基本功吉殃，這講講的都是一些進(jìn)階知識(shí)辞居，針對(duì)DP有一定基礎(chǔ)的同學(xué)。

二進(jìn)制優(yōu)化

這類問題一般是這樣的蛋勺，我們有一個(gè)數(shù)字K瓦灶，我們需要枚舉他的1~K 這里的所有可能。
比如經(jīng)典的背包問題抱完，有一個(gè)商品只剩7個(gè)了贼陶。我們?nèi)绻阉?dāng)做01背包來處理，可以把這個(gè)商品看成巧娱，1個(gè)一種碉怔，2個(gè)合并拿為另一種，3個(gè)合并拿為第三種禁添。撮胧。。一直到7個(gè)老翘。當(dāng)然7種可能里只能選1種可能芹啥，他們之間是互斥的，所以需要放到枚舉體積的循環(huán)內(nèi)铺峭。
這樣子時(shí)間復(fù)雜度是 背包容量 * 物品種類 * 物品個(gè)數(shù)墓怀。
我們來看下代碼

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++) { // 枚舉此種物品個(gè)數(shù)
                if (k * curWei > j) break;
                dp[j] = Math.max(dp[j], dp[j - k * curWei] + k * curVal);
            }
        }

    }
    return dp[W];
}

下面就引入了2進(jìn)制優(yōu)化的思考，7在二進(jìn)制表示下是111. 那么我們其實(shí)可以用100,010,001.進(jìn)行組合而表示出所有7種可能性卫键。比如這3個(gè)數(shù)字全不選是000傀履， 選第一和第三個(gè)就能組合出101.
所以我們其實(shí)可以不用枚舉所有的7種可能性，我們只要組合出3種可能性就好莉炉。 這里的3其實(shí)是7的LOG钓账。

所以時(shí)間復(fù)雜度 那一維的時(shí)間復(fù)雜度可以優(yōu)化到LOG N碴犬。
在繼續(xù)深入下去之前，我們可以先看一道這個(gè)思想的題熱個(gè)身官扣。
https://leetcode.com/problems/patching-array/
這道題就差不多是類似的思想翅敌，我需要加進(jìn)去哪些數(shù)，就可以組合出所有的1~N的數(shù)惕蹄。這題就是判最小的那個(gè)未滿足的數(shù)是幾蚯涮，把它引入。然后找下一個(gè)未滿足的卖陵。如果下一個(gè)滿足遭顶，就把這個(gè)范圍拉大。比如[1,3,10] 要組合出11以內(nèi)的數(shù)泪蔫。先看1有沒有棒旗，有了加進(jìn)來，sum=1撩荣。發(fā)現(xiàn)2沒有铣揉，所以要補(bǔ)2. sum=3. 3 < sum ，加進(jìn)來餐曹。 sum = 6. 然后就會(huì)發(fā)現(xiàn)7沒有逛拱，要補(bǔ)7。依次類推台猴。
而我們這里的思想是把一個(gè)數(shù)拆成盡可能少的數(shù)朽合，使得他們的組合出來的全集是1~這個(gè)數(shù)的集合。

這里和之前不一樣的地方是組合饱狂。也就是說我們之前把7種物品是看成互斥的（選了里面1個(gè)曹步，就不能再選另外6個(gè)），而現(xiàn)在我們可以把這3種物品看成不互斥的（為了讓他們能組合起來休讳，選了一個(gè)還有機(jī)會(huì)選另一個(gè)）
所以我們要把這層循環(huán)放到W之前讲婚。其實(shí)暗示的含義是這樣我們把7個(gè)的A物品，變成了B物品（001）俊柔，C物品（010）磺樱，D物品（100）。每種都可以選1次或選0次婆咸。
如果總數(shù)是8個(gè)， 我們需要一個(gè)B物品(001), C物品(010), D物品(100),但是這樣我們只能表示所有0-7的可能芜辕，而此時(shí)無法引入（1000）尚骄，因?yàn)椴]有15 個(gè)物品這么多。所以最后一個(gè)（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) { // 枚舉此種物品個(gè)數(shù)
            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];
}

下面我們來看另一個(gè)問題侵续，這里會(huì)講2個(gè)優(yōu)化

https://leetcode.com/problems/sliding-window-maximum/
這道題是非常經(jīng)典倔丈，就是求滑動(dòng)窗口的最大值憨闰。我們知道求滑動(dòng)窗口的，一般維護(hù)2個(gè)指針就好需五。然后左指針和右指針移動(dòng)的時(shí)候看怎么更新狀態(tài)鹉动。比如求窗口中位數(shù)。我們維護(hù)2個(gè)堆宏邮，一個(gè)大根堆存小的一半的數(shù)泽示。一個(gè)小根堆存大的一半的數(shù)。左右指針滑的時(shí)候蜜氨，我們可以知道這個(gè)數(shù)應(yīng)該要從哪個(gè)堆移除械筛，和加入。
而最大值稍微復(fù)雜一些飒炎，如果我們只是維護(hù)一個(gè)目前的最大值埋哟，如果新加進(jìn)來的數(shù)比最大值大則更新。但是新離開的數(shù)和最大值一樣的話就麻煩了郎汪。我們沒有維護(hù)第二個(gè)大的值赤赊。即使多維護(hù)一個(gè)第二大的變量，當(dāng)他成為最大值并離開時(shí)煞赢，我們又麻煩了抛计。那其實(shí)是要維護(hù)窗口內(nèi)的所有數(shù)了。
這個(gè)時(shí)候耕驰，我們要思考的點(diǎn)是一個(gè)數(shù)什么時(shí)候是無用數(shù)爷辱，無用數(shù)就是他的存在沒有任何可能去改變結(jié)果。比如【9,8,7,6】這里沒有無用數(shù)朦肘，因?yàn)殡m然一開始是9是老大饭弓，但是窗口右移，之后每個(gè)數(shù)都有機(jī)會(huì)去做老大媒抠。我們?cè)倏匆唤M數(shù)[1,2,3,4]. 如果是求最大值弟断，那么前3個(gè)是徹底沒用的，如果窗口是4的話趴生，因?yàn)?的存在他們是絕對(duì)不會(huì)成為任何一個(gè)窗口的最大值阀趴。
這里其實(shí)引入了數(shù)據(jù)特權(quán)的2個(gè)維度。這和打德州撲克很像苍匆，即使你牌不夠大刘急，如果你的位置有優(yōu)勢(shì)，總體優(yōu)勢(shì)不一定只看牌的大小浸踩。而這里的數(shù)據(jù)其實(shí)也是這2個(gè)維度叔汁，一個(gè)是位置，一個(gè)是大小。只有當(dāng)2維都落后時(shí)据块，這時(shí)才是無用數(shù)码邻。
我們來重新定義一下無用數(shù)。就是位置和大小都比當(dāng)前窗口的某一個(gè)數(shù)要差另假，那么就可以直接丟棄這個(gè)數(shù)像屋。這個(gè)背后的思想也就是單調(diào)棧和單調(diào)隊(duì)列優(yōu)化的思想。
我們?cè)谶M(jìn)棧的時(shí)候边篮，可以去看己莺，前面的數(shù)一般算位置比自己差的，因?yàn)槲沂呛筮M(jìn)棧（后浪之后還有無限可能）如果前浪除了剩余時(shí)間少苟耻，另一個(gè)維度也輸給了后浪篇恒，前浪就可以出棧了。
按照這個(gè)思想凶杖，因?yàn)槲覀円氖亲畲笾敌布瑁覀兒罄藖淼臅r(shí)候，如果是最大的智蝠，其實(shí)是可以把所有前浪都彈出去腾么，直到遇到一個(gè)更大的前浪，他就安靜的待在他后面杈湾，直到時(shí)間流逝（窗口滑動(dòng)）解虱，前浪自然離開，這個(gè)后浪就登上了歷史舞臺(tái)漆撞，前提是沒有更后浪把他帶走殴泰。
這樣看單調(diào)棧的思想其實(shí)還蘊(yùn)含著一定的社會(huì)規(guī)律。
基于上述思想浮驳，隊(duì)列頭部就是最大的數(shù)了悍汛。每次滑動(dòng)的時(shí)候，需要看看至会，這個(gè)數(shù)的壽命是不是到了离咐。如果到了就把他從隊(duì)頭彈出，那么之后就是第二大的了奉件。當(dāng)一個(gè)數(shù)新進(jìn)來時(shí)宵蛀，就看看有沒有混得比自己差的前浪，讓他們從隊(duì)尾彈出县貌。
所以單調(diào)隊(duì)列的本質(zhì)是一群年齡從老到小的數(shù)據(jù)术陶，維持了本事從高到底的排序這就是單調(diào)的來由

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]); // 后浪入隊(duì)等待機(jī)會(huì)
        if (i >= k - 1)
            res[idx++] = dq.peekFirst(); // 后浪登上歷史舞臺(tái)
    }
    return res;
}

在深入一些

我們之前講到了數(shù)據(jù)的2個(gè)維度。并結(jié)合這個(gè)來思考如何讓后浪淘汰前浪煤痕，而引出了單調(diào)隊(duì)列和單調(diào)棧瞳别。下面又是一個(gè)很經(jīng)典的問題征候，叫最長(zhǎng)（最短）子數(shù)組的和滿足XXX條件。
比如https://leetcode.com/problems/minimum-size-subarray-sum/
這道題祟敛。
要求的是最短的子數(shù)組和要>=S。題目說明數(shù)組里全是正數(shù)兆解。這是一個(gè)經(jīng)典的可變長(zhǎng)度的滑動(dòng)窗口馆铁，窗口為了要盡可能的小，所以一旦滿足條件锅睛，左側(cè)就開始收縮埠巨，直到不再滿足條件為止。更新MIN SIZE现拒。然后繼續(xù)移動(dòng)右側(cè)使得滿足條件辣垒。
這種算法其實(shí)和做企業(yè)很像，右指針是不斷去開拓新的可能印蔬，找到了盈利模式后勋桶。移動(dòng)左指針，不斷去壓縮成本侥猬，保持自己的競(jìng)爭(zhēng)優(yōu)勢(shì)例驹。
當(dāng)然上面的假設(shè)很美好，因?yàn)樗械臄?shù)據(jù)都是正數(shù)的退唠，所以我們可以保證的是鹃锈，我們的每一次努力，都是正反饋（不可能移動(dòng)了左指針瞧预，成本反而比之前高）
但是現(xiàn)實(shí)并不一定這么美好屎债，因?yàn)橛泻芏辔粗獢?shù)」赣停可能辛苦付出的研發(fā)投入盆驹，最后被證明是毫無價(jià)值的。那么在含有負(fù)數(shù)的時(shí)候應(yīng)該怎么考慮這類問題呢秸苗？
其實(shí)這也對(duì)應(yīng)了一道LEETCODE 題目召娜，這題就變成了HARD了。生活其實(shí)就都是HARD這樣的惊楼。
https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/
如果引入了負(fù)數(shù)玖瘸，我們其實(shí)就沒有了滑動(dòng)窗口永遠(yuǎn)是正反饋的性質(zhì)，那么窗口的不變量就變成了變量檀咙。這個(gè)時(shí)候比較容易想到的是構(gòu)建前綴和數(shù)組雅倒，然和暴力枚舉所有窗口的可能，用前綴和相減O(1)得到是否滿足條件弧可，并更新最短蔑匣。這樣窗口的窗口可能是O(N^2)的復(fù)雜度。

只能這樣了嗎？

在現(xiàn)實(shí)中我們遇到這樣一個(gè)問題該如何破局呢裁良？
如果是我凿将，我會(huì)先盡一切可能找到一個(gè)可以滿足要求的方案，然后再想怎么去優(yōu)化价脾。
那么我就先忘記最短這個(gè)條件牧抵，因?yàn)闊o論多短，都要先滿足>=k.
那么我就從PRESUM 里去找侨把，當(dāng)我站在這個(gè)PRESUM時(shí)犀变，我希望做的是之前有沒有一個(gè)PRESUM 可以使得我們相減能滿足條件。如果有秋柄，那么我再想優(yōu)化获枝，他是否是離我距離最短。
講到這里你是不是發(fā)現(xiàn)了什么骇笔？對(duì)的省店，距離。又是你蜘拉，出現(xiàn)了萨西。前浪和后浪。
這里就像是找能一起完成任務(wù)的伙伴旭旭，如果有多個(gè)谎脯，我要選同齡人（共同話題多，代溝少持寄，何樂為不為）
那么無用數(shù)也就很明顯了源梭。因?yàn)檫@里是要減去一個(gè)之前的PRESUM。為了使得我能完成任務(wù)（>= K）的概率盡可能高就意味著減去的數(shù)越小越好稍味。（更有機(jī)會(huì)使得結(jié)果更大废麻，更大就意味著更多可能>=K）
那么首先要保證任務(wù)完成，所以數(shù)值更小的PRESUM不能丟模庐。其次是完成任務(wù)前提下烛愧，我希望數(shù)組長(zhǎng)度越短。那么如果一個(gè)數(shù)又大又遠(yuǎn)掂碱，就是無用數(shù)了怜姿。
單調(diào)隊(duì)列的本質(zhì)是一群年齡從老到小的數(shù)據(jù)，維持了本事從高到底的排序
這里的本事是PRESUM 小疼燥，所以單調(diào)隊(duì)列里隊(duì)頭是最小值沧卢。
我們當(dāng)前這個(gè)PRESUM如果能和隊(duì)頭碰出火花了，其實(shí)隊(duì)頭的使命就結(jié)束了醉者。因?yàn)樗麤]必要再和我之后更年輕的人組隊(duì)但狭，因?yàn)榇鷾现粫?huì)更大披诗。而我，會(huì)不斷彈出隊(duì)頭立磁，直到一個(gè)人和我完成不了任務(wù)呈队。那么我就知道和誰做任務(wù)代溝最小了。因?yàn)殛?duì)列里的本事是單調(diào)遞減的（隊(duì)頭完不成息罗，之后的人雖然年輕但也還是完不成的）
說到這里我想你應(yīng)該直到怎么做這題了吧掂咒。

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++) {
        // 優(yōu)先確保有解，因?yàn)榍岸耸亲钚〉穆鹾恚仍囎钚〉?gt;=K 的概率最大
        while (!inc.isEmpty() && presum[i] - presum[inc.peekFirst()] >= K) {
            res = Math.min(res, i - inc.pollFirst());
        }
        // 保持單調(diào)性
        while (!inc.isEmpty() && presum[i] <= presum[inc.peekLast()]) {
            inc.pollLast();
        }
        inc.offerLast(i);
    }
    return res == l + 1 ? -1 : res;
}

現(xiàn)在我們?cè)賮砜纯匆悄繕?biāo)是要求SUM <= K 該怎么做呢？

其實(shí)這就是數(shù)據(jù)的本事?lián)Q了定義温圆，之前我們認(rèn)為挨摸，數(shù)值越小的越有本事。是因?yàn)闇p去小的岁歉，我可以有更大的概率滿足>=K的條件〉迷耍現(xiàn)在就是反過來了。為了讓相減之后锅移，盡可能小熔掺。那么數(shù)值大的被認(rèn)為是本事大。所以只要把單調(diào)遞增隊(duì)列 變成遞減即可非剃。
下面給大家留一道思考題置逻，如果是求最長(zhǎng)的SUBARRAY 要求SUM >= K 或 <= K 該怎么做呢？

回到滑動(dòng)窗口最大值

上面我們已經(jīng)講了單調(diào)隊(duì)列的算法是怎么一回事备绽。下面我們?cè)賮砜纯催@道題的另一個(gè)做法券坞。
因?yàn)榇翱诖笮∈枪潭ǖ模覀冊(cè)谌我欢温錄Q定的他的值是有限的數(shù)據(jù)肺素。假設(shè)我們把所有數(shù)據(jù)全劃分為窗口大小的片段恨锚。然后對(duì)這個(gè)片段求出最大值。那么只要解決跨片段的問題就能把問題解決倍靡，一般也只需要考慮2個(gè)片段的數(shù)據(jù)猴伶，就可以得出跨片段窗口的最大值了。
下面就是思考如何用O（1）的時(shí)間去處理2邊片段的數(shù)據(jù)塌西，得到跨片段的最大值呢他挎？

image.png

不難發(fā)現(xiàn)我們只要知道左片段右半部分的最大值，和右片段左半部分的最大值就可以算出窗口的最大值雨让。
按照這個(gè)思路雇盖。我們需要維護(hù)2個(gè)DP數(shù)組，分別存儲(chǔ)每個(gè)片段的左半部分的最大值和右半部分的最大值栖忠。 然后指針滑動(dòng)的時(shí)候取MAX就可以O(shè)(1)時(shí)間輕松拿到解崔挖。

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;
}

上面的思路也是非常經(jīng)典贸街。我們下面想想這個(gè)問題的更一般形式。一個(gè)數(shù)組狸相，我們?nèi)绾卧贠(1)時(shí)間求出任意窗口的最大值呢薛匪。
繼承上面的思路，我們知道如何用窗口大小的K 來在O(1)時(shí)間找出任意窗口為K的最大值脓鹃。那么我們?cè)陬A(yù)處理的時(shí)候逸尖，只要把K從1枚舉到N就可以了。然后查找就是O(1)的了瘸右。
其實(shí)這個(gè)思路一點(diǎn)沒有毛病娇跟，因?yàn)樵谶@種做法下，等價(jià)于把所有要查詢的可能給CACHE住了太颤。其實(shí)我們可以先想下有了K值的LEFT數(shù)組和RIGHT數(shù)組苞俘，可以用O(2)的時(shí)間解決2 * K的窗口嗎？
這個(gè)應(yīng)該非常好想龄章。把2個(gè)K的窗口的最大值求出來然后對(duì)這2個(gè)最大值給取MAX吃谣。
那K~ 2 * K - 1的窗口該如何求最大值呢？
其實(shí)用K值的LEFT和RIGHT數(shù)組也是可以求的做裙， 只不過這個(gè)時(shí)候2個(gè)窗口中間會(huì)有重疊的部分岗憋，不過對(duì)取MAX沒有任何影響。
如下圖锚贱，K=3仔戈， 求窗口為4（紅色）的最大值⊥锱福可以用這樣2個(gè)K=3的窗口（綠色和藍(lán)色）最大值給求解出來杂穷。

image.png

這種做法再處理2 * K 以上的窗口，隨著窗口越來越大卦绣，性能會(huì)越來越慢耐量。所以我們就需要引入更大一些的K。這樣在處理大窗口的時(shí)候就用大K滤港，小窗口用小K廊蜒。這個(gè)跟做測(cè)量是一樣的，你要測(cè)量一直鉛筆需要一把直尺就好了溅漾。要是要測(cè)量頭發(fā)絲就需要螺旋測(cè)微器山叮。
那么我們需要思考的就是如何構(gòu)建出一套最精簡(jiǎn)的工具包使得，任意窗口K都可以有對(duì)應(yīng)的工具添履，立刻量出屁倔。
這又回到了我們的2進(jìn)制思想。比如窗口大小的二進(jìn)制為(101101)暮胧，我們只需要用最高位是1锐借，剩余位全0(10000)的工具就一定可以覆蓋住它.
32的工具 可以覆蓋掉32-63的所有最大值計(jì)算问麸，原理如上圖左右2邊分別計(jì)算出2個(gè)32的最大值，取最大
那么這樣我們最多只要構(gòu)建31組工具钞翔，就可以實(shí)現(xiàn)所有窗口的O(1)測(cè)量了严卖。
同樣是剛才那道題，我們可以直接丟工具包進(jìn)去做布轿。二進(jìn)制本質(zhì)上是LOG(N)的復(fù)雜度哮笆，所以構(gòu)建工具包的時(shí)間復(fù)雜度O(N LOG N)
這里構(gòu)建工具包有一些技巧，我們可以用低長(zhǎng)度的工具包汰扭，O(1)時(shí)間構(gòu)建出高一層長(zhǎng)度的工具包稠肘。

int[][] rangeMaxQuery(int[] nums) {
    int l = nums.length;
    int[][] dp = new int[l][20]; //dp[i][j] = 從i 開始，長(zhǎng)度為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]) 低長(zhǎng)度工具包構(gòu)建高長(zhǎng)度工具包
            // 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;
}

有了上面這個(gè)工具包萝毛，我們?cè)偾蟠翱谧畲笾禃r(shí)只需
res[i] = Math.max(dp[i][num], dp[i + k - (1 << num)][num]);
num為最高位1是第幾位（0開始計(jì)數(shù)）

二進(jìn)制優(yōu)化++

再回到今天的周賽題來,https://leetcode.com/problems/kth-ancestor-of-a-tree-node
題目給了一顆有根樹启具，要求任意節(jié)點(diǎn)的第K個(gè)祖先，如沒有返回-1. 暴力解就是從這個(gè)節(jié)點(diǎn)向上走K步珊泳，然后輸出第K個(gè)祖先】椒校可是題目的樹深可能達(dá)到50000色查，并且有50000次查詢，所以這樣做很有可能會(huì)超時(shí)撞芍。
比如我們要找第15個(gè)祖先秧了，有沒有什么快速的方式呢？我們可以用二進(jìn)制的思想序无。15的最高位1為8.那么我是否可以先跳8步验毡，看那個(gè)祖先是誰，然后基于那個(gè)祖先再找他的第7個(gè)祖先即可帝嗡。這樣子只需要LOG N的時(shí)間晶通，就可以定位了。
那么我們也是要構(gòu)造和前面一個(gè)情況一樣的工具包哟玷。這個(gè)工具包里需要擺放的是每一個(gè)節(jié)點(diǎn)狮辽，往后1步，2步巢寡，4步喉脖，。抑月。树叽。2^k步的父親節(jié)點(diǎn)是誰，如果跳過根節(jié)點(diǎn)存-1.
我們也是和上面一樣的構(gòu)造工具包的思路谦絮，先構(gòu)造一步的题诵，隨后用1步的去構(gòu)造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 來構(gòu)建 1的J
            dp[i][j] = (par == -1 ? -1 : dp[i - 1][par]);
        }
    }
}

然后來找的時(shí)候，比如找15仇轻，我們先要去跳8下的祖先京痢，然后去找該祖先的跳7下（這里再用最高位來2進(jìn)制跳）一直跳到-1，或第15個(gè)祖先退出循環(huán)篷店。

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;
}

上述就是二進(jìn)制思路的基本思想祭椰。本質(zhì)是一個(gè)數(shù)字，可以轉(zhuǎn)換到2進(jìn)制疲陕，然后依次處理二進(jìn)制的每個(gè)1方淤，而達(dá)到快速攻克某個(gè)問題的效果。
構(gòu)造工具包的時(shí)候蹄殃，一般從最底層的1携茂，依次往上構(gòu)造。
看到這里再回想一下诅岩，我們已經(jīng)講述的2進(jìn)制優(yōu)化的3個(gè)問題讳苦，分別是多重背包的二進(jìn)制優(yōu)化，區(qū)間最大值的二進(jìn)制優(yōu)化吩谦，和第K個(gè)祖先的二進(jìn)制優(yōu)化鸳谜。

單調(diào)隊(duì)列優(yōu)化

下面我們來看第二種DP優(yōu)化方式，單調(diào)隊(duì)列式廷。之前已經(jīng)講過了單調(diào)隊(duì)列是怎么一回事咐扭。他的核心就是一群年齡從老到小的數(shù)據(jù)，維持了本事從高到底的排序滑废。 新數(shù)據(jù)進(jìn)來時(shí)需要淘汰無用數(shù)蝗肪。
在一類DP問題中，我們可以用單調(diào)隊(duì)列的思想來進(jìn)行降維打擊蠕趁。我們來看我上次周賽遇到的一道題薛闪。
https://leetcode.com/problems/constrained-subsequence-sum/
這道題的意思是我們要構(gòu)造一個(gè)子序列（順序要保證，中間可以跳元素）這個(gè)子序列中間跳的元素不能超過K妻导。也就是K=2逛绵，只能跳1個(gè)元素。K=1倔韭，子序列的數(shù)之間必須相鄰术浪。
那么很快就可以想到的是根據(jù)數(shù)組長(zhǎng)度來構(gòu)建DP，DP I寿酌，來表示數(shù)組的前I項(xiàng)胰苏，且最后一項(xiàng)選中的最大值。那么最后一項(xiàng)選醇疼。前面K個(gè)數(shù)是可以有2個(gè)情況硕并，選或不選法焰。
所以轉(zhuǎn)移公式為
dp[i] = (max{j from [i - k, i)} dp[j]) + cur[i]
這里我們可以看到每一個(gè)DP需要從前面K個(gè)狀態(tài)轉(zhuǎn)移過來，那么時(shí)間復(fù)雜度就為O (N * K）
你看到這里會(huì)發(fā)現(xiàn)其實(shí)那個(gè)MAX的變量是在根據(jù)I 指針在滑動(dòng)的而且是定長(zhǎng)的倔毙。那么其實(shí)直接套上之前的滑動(dòng)窗口最大值的維護(hù)埃仪，就可以把這里O(K)的枚舉 變成O(1)的取窗口最大了。
下面是我用陕赃，數(shù)組來模擬雙端隊(duì)列的比賽時(shí)寫的一段代碼

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++; // 非空卵蛉，且壽命到了，前浪退出歷史舞臺(tái)
        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;
}

這道題還可以有一個(gè)變形么库，之前我們的限制是空擋不能大于等于K∩邓浚現(xiàn)在我們的要求是選出子序列，連續(xù)的數(shù)不能大于等于K诉儒，這里我們限制數(shù)組里的數(shù)都為正數(shù)葡缰，又應(yīng)該怎么做呢？
之前我們?yōu)榱讼拗瓶論醭婪矗笞詈笠粋€(gè)數(shù)必須拿泛释。這樣我們就可以通過枚舉前K個(gè)必拿的狀態(tài)轉(zhuǎn)移到目前MAX的不會(huì)有K空擋的狀態(tài)。
而現(xiàn)在為了不能持久連續(xù)温算，我們依賴用前K個(gè)狀態(tài)胁澳，此時(shí)已經(jīng)不要求最后一個(gè)必拿，只要結(jié)果最大即可米者。破壞連續(xù)K個(gè)的核心就是枚舉，這個(gè)不拿是K個(gè)里的什么位置宇智。
可是自己這個(gè)不拿蔓搞，然后就是DP[I-1]，也可以是DP[I-2] + ARR[I]随橘，也可以是DP[I-3] + ARR[I] + ARR[I - 1]喂分。。机蔗。這里我們發(fā)現(xiàn)了一個(gè)數(shù)組求和蒲祈，我們可以用PRESUM，來把這個(gè)求和的步驟變成O(1)
轉(zhuǎn)移公式為
dp[i] = (max{j from [i - k, i)} dp[j - 1] - presum[j]) + presum[i]
這里的意思我們確定J 不拿了萝嘁，J之前的用DP[J-1]取到最大梆掸，之后的用PRESUM求出來（因?yàn)閿?shù)都是正數(shù)可以貪心只丟一個(gè)）
而單調(diào)隊(duì)列里存的就是之前K SIZE WINDOW的 (dp[j-1] - presum[j]) 的最大值。
依舊是區(qū)間窗口最大值的維護(hù)牙言。
主代碼如下

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函數(shù)如下

int help(int i) {
    if (i == 0) return 0;
    return dp[i - 1] - presum[i];
}

總結(jié)

今天講述了DP優(yōu)化中的兩類酸钦，分別是二進(jìn)制優(yōu)化和單調(diào)隊(duì)列優(yōu)化。我們不妨回顧一下咱枉，二進(jìn)制優(yōu)化是把對(duì)數(shù)的遍歷拆成對(duì)每一個(gè)二進(jìn)制1的遍歷而提升效率卑硫。效率提升幅度為O(N)->O(LOG N)徒恋。而單調(diào)隊(duì)列的優(yōu)化通常就是維護(hù)區(qū)間最值屬性直接獲得最佳狀態(tài)減少一層狀態(tài)轉(zhuǎn)移的遍歷而提升效率。效率提升幅度為(O(K) -> O(1))
下一講會(huì)帶大家一起進(jìn)入神奇的四邊形不等式優(yōu)化和斜率優(yōu)化和快速冪優(yōu)化欢伏∪胝酰看數(shù)學(xué)是怎么幫助我們提升代碼性能的。
最后給大家留一道二進(jìn)制優(yōu)化的思考題和單調(diào)隊(duì)列優(yōu)化的思考題硝拧。

在一棵有根多叉樹中径筏，如何使用二進(jìn)制優(yōu)化，來找最近公共祖先呢河爹？

總共有 n 道題目要抄匠璧，編號(hào) 0,2,…,n，抄第 i 題要花 ai 分鐘咸这。老師要求最多可以連續(xù)空的題為K夷恍，求消耗時(shí)間最少滿足老師要求的方案。