面試向算法 - 二分法專題(二)

前言

在我看來，大部分面試的算法題從來都不是難在思維，而是缺乏系統的教學。它不像數學屬於普及的基礎教育，算法題目的大部分知識、技巧往往都局限於 competitive programming 當中 (比如各種 OI 競賽、 ACM 競賽等)，這些都是大部分計算機行業從業者接觸不到的。它就像一個大群體中一個半封閉的小群體一樣，系統的知識就在那裡，只是我們很少會主動走進去。因此，我期望將這些知識給帶出來，就引申出了本系列文章和視頻。

在 《二分法（一）》當中我們已經分別講解了：

那麼，本篇的主要內容即是對剩下的四種應用進行深入分析。

最大/最小平均值(max/min average)

注意：搭配 B 站視頻更香奧！

正文 類型二：對結果進行二分

這類問題仍然屬於最優化問題，該問題的所有方案組成問題的 值域，需要求所有方案中的最優方案。

而上述通過二分法能夠處理的最優化問題需要滿足：值域 滿足某種特殊的單調性。用更加詳細的話講，就是能夠通過題目特性將值域分成兩個區間，一個區間滿足特性，另外一個區間不滿足特性

我們來看具體的例子：leetcode: 1011. 在 D 天內送達包裹的能力[1]

(圖 5.1)

題目需要求 D 天內能夠傳送所有包裹的最低運載能力，假設這個 最低運載能力 為 x。那麼很顯然 x+1 也能夠在 D 天內運完所有包裹。因此本題的 check 特性 就是 能在 D 天內運完所有包裹。我們可以根據該特性將值域分為兩個區間：

(圖 5.2)

那麼值域的範圍是多少呢？左邊界肯定不能

這裡值得注意的是，有些題目不會給出右邊界，因此我們需要根據經驗寫出右邊界，比如 。

分析到這裡，算法思路就結束了。最後結果 右區間的左端點，可以通過模板一來寫。而 check() 方法可以很容易根據定義用貪心寫出來。

def check(x):
    cnt = 0 # 統計傳輸天數
    curr = 0 # 當前的重量，不能超過 x

    for t in weights:
        if t > x: return False # 如果單個物品超過 x, 很明顯表示該運載能力不夠
        
        curr += t  # 加上當前物品，看看是否會超重，超重的部分下一次再運
        if curr == x:
            cnt += 1
            curr = 0
        elif curr > x:
            cnt += 1
            curr = t
    
    if curr > 0: cnt += 1 # 最後還剩餘 curr(不超過運載能力)，只能放在下一次再運 
    return cnt <= D # 根據判斷總運輸天數是否超過 D，來判斷該 x 能夠滿足要求
本算法的時間複雜度為 
有同學可能會問，該題的暴力樸素解法是什麼？
其實也很簡單，組合數學。將數組切分成 D 個區間，不同的切分方式為不同的方案。最優方案是 
而我們根據題目中隱含的單調性將複雜度極大地降低，下面我們來看看同類型的其他題目，首先給出個定義。
在值域上二分的這類題目，其代碼區別主要在 check 方法，不同的題目會結合其他算法來進行考察。比如 leetcode: 778. 水位上升的泳池中遊泳[2]
(圖 5-3)
本題看似是個 hard 級別難度，如果你理解上上述的思路後，本題就變成了一個 easy 級別的。
同樣來分析題目，假設最少耗時為 t, 很明顯 t+1 也能夠到達右下角，而 t-1 不能。所以本題 值域是滿足單調性的。
所以我們可以二分值域，答案就是右區間的左端點。而本題不一樣的是 check() 方法，我們需要通過 dfs 來判斷值域中的值是否滿足題目要求。
l = 0 # 二分部分
r = 2500
while l < r:
    mid = (l+r)//2

    if check(mid): r = mid
    else: l = mid+1

return l
def check(t):
    if t < grid[0][0]: return False # 特判 (0, 0) 點

    vis = [[False]*n for i in range(n)] # 保存當前節點是否被訪問過
    dx = [1, -1, 0, 0] # 常見 dfs 寫法
    dy = [0, 0, 1, -1]

    vis[0][0] = True

    def dfs(x, y): # dfs 過程
        if x == n-1 and y == n-1: # 到達右下角
            return True
        
        for i in range(4):
            x1 = dx[i] + x
            y1 = dy[i] + y

            if x1 >= 0 and x1 < n and y1 >= 0 and y1 < n and not vis[x1][y1] and grid[x1][y1] <= t:
                vis[x1][y1] = True
                if(dfs(x1, y1)): return True

        return False
    
    if dfs(0, 0): return True # 調用 dfs
    else: return False
由於到目前為止，dfs 我們還沒有講過，所以這裡就不詳解介紹了，後續課程再說。
理解了本類題型，下面 18 道題目就很簡單了，作為課後習題留給大家。
leetcode: 1482. 製作 m 束花所需的最少天數[3]leetcode: 1292. 元素和小於等於閾值的正方形的最大邊長[4]leetcode: 875. 愛吃香蕉的珂珂[5]acwing(頭條 2019 筆試):680. 剪繩子[7]acwing(第八屆藍橋杯): 1227. 分巧克力[8]acwing(頭條 2019 筆試): 730. 機器人跳躍問題[9]leetcode: 793. 階乘函數後K個零[12]leetcode: 719. 找出第 k 小的距離對[13]類型三：
另一類可以被單獨拿出來的問題被稱為求  。這類問題的出現頻率很高且可以通過二分法來解決。
我們先通過一道簡單的題目來看看為什麼被稱為  -  leetcode: 410. 分割數組的最大值[14]。
圖 5-4
（圖 5-4）
本題雖然標為 hard 級別，但仍然屬於入門的難度。根據題意，需要設計一個算法，使 m 個子數組各自和的最大值最小，轉換為更簡單的公式就是：，這裡假設最終結果為 t，可以直接得出下面三個推論：
一定存在一種切割方式使得 
所以，值域範圍是存在單調性的。
而我們求的 右區間的左端點，用整數域二分模板一就在合適不過了。
而具體的值域為 。
代碼的主要區別仍然是在 check() 方法的實現上。前面我們有講過，可以通過貪心來實現。具體為什麼呢？儘管貪心的數學證明一直是個不太好處理的事（一般通過反證法或者構造法來證明）。我們仍然可以構造出貪心策略來 - 每次切割時使切割開的區間和儘可能靠近傳入的 。如下代碼所示：
def check(x: int) -> bool:
    total, cnt = 0, 1 # cnt 為 1 是由於剩下最後的部分沒有處理
    for num in nums:
        if total + num > x:
            cnt += 1
            total = num
        else:
            total += num
    return cnt <= m
下面我們看一道 NOIP 2015 提高組 的一道題 - acwing: 519. 跳石頭[15]。
（圖 5-5）
題目要求給出 最多移走 M 塊石頭之後，最短跳躍距離的最大值，轉換成公式就是 。
假設該值為 ，同樣可以得出 3 個推論：
值域滿足單調性，可以根據是否存在移動方法將 值域範圍分為兩個區間。
很明顯，這是求左區間的右端點，用模板二的代碼即可。稍微變化的仍然是 
def check(x):
    
    cnt = 0 # 統計需要移動的石頭數量
    last = 0 # 上一個未移動的石頭位置
    for i in range(1, n+1):
        if d[i] - last < x: # 如果當前石頭到上一個未移動石頭距離不足 x，則當前石頭需要被移走
            cnt += 1
        else:
            last = d[i]
    
    return cnt <= m
是不是很簡單就解決了看似 hard 級別的題目，如果題目想出的更加複雜一點，可以將二分和圖論結合，比如課後習題中的一道，這裡就不講了（如果不會，可以在答疑群裡面提出）
課後習題（6 道）
leetcode plus: 774. minimize-max-distance-to-gas-station[16]類型四 - 求最大平均值 / 最小平均值
第四類可以通過二分法可以解決的有趣問題就是 最大平均值/最小平均值。舉個抽象的例子，假設存在一個數組 
(圖 5-6)
題意告訴我們每個可能方案需要滿足 區間大小 ，那麼暴力樸素的思路是什麼？
枚舉所有可能的方案，而方案數為 , 而判斷單個方案的時間複雜度是多少呢？
樸素做法是 前綴和技巧 達到 
我們將上述題意用公式表示出來就是：，假設結果為 
很顯然，值域 具有單調性，可以劃分為兩個區間：（這裡使用 
由於 值域 是實數域，所以我們可以直接套用 實數二分模板即可。
那麼該如何判斷某個值  - 也就是 
對於所有 最大平均值/最小平均值 的思路是類似的（大家多手推幾遍就有感覺了，算是通用思路），需要進行如下圖 5-7 所示的變形即可：
（圖 5-7）
在這裡，我們運用了簡單的 一維前綴和 和 貪心 的優化（具體技巧在後續課程會詳細講解），將 
def check(x):
    s = [0] * (n+1)
    minV = [0] * (n+1)
    for i in range(1, n+1):
        s[i] = s[i-1] + a[i] - x
        minV[i] = min(minV[i-1], s[i])
    
    for i in range(m, n+1):
        if s[i] - minV[i-m] >= -1e-6: # 值得注意，由於是浮點數，所以在一定範圍保證精確即可
            return True
    
    return False
最後由於我們要取下底取整，需要 math.floor(r*1000)。
題目 acwing: 02. 最佳牛圍欄[20] 就是直接對上題進行了描述的替換，思路和分析模型完全一模一樣，這裡就不再重複了。
本題除了二分，還有通過斜率求解的 
同樣，如果我們想要稍微增加本類題目的難度，可以將其與其他基礎算法結合，比如圖論，同樣的課後習題中 codeforces edu 中有一題即使如此。
課後習題（共 6 題）：
acwing: 361. 觀光奶牛(圖+二分)[23]類型四 - 求某種特殊的第 k 大 / 小
最後一類要介紹的是在一個或多個有序數組中尋找合併後的第 快速選擇算法 或者還未講到的 堆 來實現，但是下面要講的題目無法非常方便的通過這兩種算法來求解（要麼時間複雜度過大、要麼代碼實現過於複雜）。
我們先來看 leetcode: 668. 乘法表中第k小的數[25]：
（圖 5-8）
樸素方式是先將所有序列合併然後直接得出 第 k 小數，如果合併方式是 堆 的方式，那麼時間複雜度為 
根據題意，第 
假設第 
對於任意的 
所以，上面兩個結論對於整個值域是具有單調性的，比如我們可以構造：右區間的左端點（構造左區間右端點也同樣的思路）。
那麼如何快速求得 
本類題目的第二個特性就是有序序列符合某種連續性。
比如乘法表：
因此，我們可以在 那麼算法總體的時間複雜度就是
def check(x):
    cnt = 0

    for i in range(1, m+1):
        cnt += min(x // i, n) 
    
    return cnt >= k
非常容易的就通過二分思路解決看似 hard 級別的題目。
下面我們來看一道稍微變化的題目，leetcode: 878. 第 N 個神奇數字[26]，雖然是 hard 級別，但是難度仍然不高：
（圖 5-9）
樸素做法是在 神奇的 特性，統計的策略是：
但是該時間複雜度達到 
那麼題意是否有什麼特性來降低複雜度呢？假設第 
那麼根據上面的特性將 右區間的左端點，使用模板一代碼即可。
def gcd(a, b):
    return gcd(b, a % b) if b else a 

def check(x):
    cnt = x // A + x // B  - x // LCM

    return cnt >= N

l = 1
r = N * min(A, B)

LCM = A // gcd(A,B) * B 
求最小公倍數，我們就直接通過歐幾裡得算法求出最大公約數來得到了。
課後習題（共 5 題）：
leetcode: 786. 第 K 個最小的素數分數[27]其他涉及題目
在算法題目中結合多種技巧解決一道題目是很常見的事，下面就給大家列舉一些二分法結合其他算法的題目，這些題目就不講解了，有問題可以在答疑群裡面提出來。
數學+二分：
628. 美麗的數（google kickstart 2016 round E problem B）[31]
二分+dp： acwing: 472. 跳房子[32]
二分+差分：acwing: 503. 借教室[33]
貪心+二分：  LIS 問題（動態規劃專題講解）
總結 
二分法專題到這裡就基本結束了，本專題總共涉及到 60 道 題目，以 LeetCode 難度劃分基本屬於 hard 和 medium 偏上的題目，類似的題目還有很多，但是基本都大同小異。掌握了本篇的這幾種主要題型，相信大家以後再面對二分類題目時就可以信手拈來了。
最後我們再回顧下我們的內容：通常我們將二分法分為整數域上的二分和實數域上的二分。
整數二分的細節在於終止邊界、左右區間取捨時的開閉情況，來避免漏掉答案或者造成死循環。模板一 和 模板二
通用 5 種二分類型題目為：
最大/最小平均值(max/min average)參考資料[1]
leetcode: 1011. 在 D 天內送達包裹的能力: https://leetcode-cn.com/problems/capacity-to-ship-packages-within-d-days/
[2]
leetcode: 778. 水位上升的泳池中遊泳: https://leetcode-cn.com/problems/swim-in-rising-water/
[3]
leetcode: 1482. 製作 m 束花所需的最少天數: https://leetcode-cn.com/problems/minimum-number-of-days-to-make-m-bouquets/
[4]
leetcode: 1292. 元素和小於等於閾值的正方形的最大邊長: https://leetcode-cn.com/problems/maximum-side-length-of-a-square-with-sum-less-than-or-equal-to-threshold/
[5]
leetcode: 875. 愛吃香蕉的珂珂: https://leetcode-cn.com/problems/koko-eating-bananas/
[6]
leetcode: 287. 尋找重複數: https://leetcode-cn.com/problems/find-the-duplicate-number/
[7]
acwing(頭條 2019 筆試):680. 剪繩子: https://www.acwing.com/problem/content/682/
[8]
acwing(第八屆藍橋杯): 1227. 分巧克力: https://www.acwing.com/problem/content/description/1229/
[9]
acwing(頭條 2019 筆試): 730. 機器人跳躍問題: https://www.acwing.com/problem/content/description/732/
[10]
acwing: 1028. 複製書稿: https://www.acwing.com/problem/content/description/1030/
[11]
codeforces edu 8 道題目: https://codeforces.com/edu/course/2/lesson/6/2/practice
[12]
leetcode: 793. 階乘函數後K個零: https://leetcode-cn.com/problems/preimage-size-of-factorial-zeroes-function/
[13]
leetcode: 719. 找出第 k 小的距離對: https://leetcode-cn.com/problems/find-k-th-smallest-pair-distance/
[14]
leetcode: 410. 分割數組的最大值: https://leetcode-cn.com/problems/split-array-largest-sum/
[15]
acwing: 519. 跳石頭: https://www.acwing.com/problem/content/521/
[16]
leetcode plus: 774. minimize-max-distance-to-gas-station: https://leetcode-cn.com/problems/minimize-max-distance-to-gas-station/
[17]
acwing: 2436. 串分割: https://www.acwing.com/problem/content/description/2438/
[18]
codeforces 4 道經典題目: https://codeforces.com/edu/course/2/lesson/6/3/practice
[19]
a_0, a_1, ... , a_{n-1}]
[20]
acwing: 02. 最佳牛圍欄: https://www.acwing.com/problem/content/description/104/
[21]
acwing: 2430. 送禮物: https://www.acwing.com/problem/content/description/2432/
[22]
某公司筆試題: https://www.acwing.com/community/content/537/
[23]
acwing: 361. 觀光奶牛(圖+二分): https://www.acwing.com/problem/content/description/363/
[24]
codeforces 3 道經典題目: https://codeforces.com/edu/course/2/lesson/6/4/practice
[25]
leetcode: 668. 乘法表中第k小的數: https://leetcode-cn.com/problems/kth-smallest-number-in-multiplication-table/
[26]
leetcode: 878. 第 N 個神奇數字: https://leetcode-cn.com/problems/nth-magical-number/
[27]
leetcode: 786. 第 K 個最小的素數分數: https://leetcode-cn.com/problems/k-th-smallest-prime-fraction/
[28]
acwing: 1236. 遞增三元組: https://www.acwing.com/problem/content/description/1238/
[29]
codeforces 3 道經典題目: https://codeforces.com/edu/course/2/lesson/6/5/practice
[30]
leetcode: 483. 最小好進位: https://leetcode-cn.com/problems/smallest-good-base/
[31]
628. 美麗的數（google kickstart 2016 round E problem B）: https://www.acwing.com/problem/content/description/630/
[32]
acwing: 472. 跳房子: https://www.acwing.com/problem/content/description/474/
[33]
acwing: 503. 借教室: https://www.acwing.com/problem/content/description/505/