在算法刷題和面試準(zhǔn)備中LeetCode 上的“區(qū)間加法 II”是一道看似簡單實則能有效考察對問題本質(zhì)理解和優(yōu)化思維的經(jīng)典題目。很多同學(xué)初次接觸時可能會不假思索地選擇模擬整個操作過程結(jié)果在較大的數(shù)據(jù)規(guī)模下遭遇超時。本文將帶你深入剖析力扣第 598 題從最直觀的暴力解法入手逐步推導(dǎo)出最優(yōu)的數(shù)學(xué)解法并用 Python 實現(xiàn)。無論你是正在入門算法的新手還是希望鞏固優(yōu)化思路的進(jìn)階開發(fā)者都能通過本文掌握“降維打擊”的解題技巧提升解決同類區(qū)間覆蓋問題的能力。1. 背景與核心概念在開始解題之前我們首先要明確題目到底在問什么以及它背后考察的核心算法思想是什么。1.1 問題描述與場景還原力扣 598. 區(qū)間加法 II的官方描述如下給定一個初始元素全部為0大小為m x n的二維矩陣M。同時給你一系列操作ops其中每個操作用一個包含兩個正整數(shù)a和b的數(shù)組表示含義是對矩陣M中所有滿足0 i a且0 j b的元素M[i][j]進(jìn)行加一操作。你需要執(zhí)行完所有操作后返回矩陣中最大整數(shù)的個數(shù)。通俗解釋想象你有一張m行n列的方格紙一開始所有格子都是0?，F(xiàn)在你得到一系列指令ops每個指令告訴你“請把左上角區(qū)域即前a行、前b列這個矩形范圍內(nèi)的所有格子都加上1”。你需要執(zhí)行所有指令最后看看整張紙上最大的數(shù)字是多少并且數(shù)一數(shù)有多少個格子是這個最大數(shù)字。示例 1輸入: m 3, n 3, ops [[2,2], [3,3]] 輸出: 4 解釋: 初始矩陣 M [[0, 0, 0], [0, 0, 0], [0, 0, 0]] 執(zhí)行操作 [2,2] 后M [[1, 1, 0], [1, 1, 0], [0, 0, 0]] 執(zhí)行操作 [3,3] 后M [[2, 2, 1], [2, 2, 1], [1, 1, 1]] 最大整數(shù)是 2共有 4 個值為 2 的元素。因此返回 4。1.2 核心考察點(diǎn)與常見誤區(qū)這道題被標(biāo)記為“簡單”但其真正的價值在于引導(dǎo)我們思考如何避免不必要的計算。它主要考察以下幾個點(diǎn)問題抽象能力能否將二維矩陣的多次區(qū)間加操作抽象為一個更簡單的數(shù)學(xué)問題。優(yōu)化思維當(dāng)m,n和操作次數(shù)可能很大時例如達(dá)到10^4量級模擬每一步加法時間復(fù)雜度 O(k * m * n)是完全不可行的。必須尋找規(guī)律。邊界條件處理當(dāng)操作列表ops為空時應(yīng)該如何處理常見的誤區(qū)就是陷入“模擬”的思維定式試圖真的去構(gòu)建這個矩陣并執(zhí)行所有加法操作。這不僅效率低下也錯過了題目設(shè)計的精妙之處。2. 環(huán)境準(zhǔn)備與思路分析在動手寫代碼之前我們先搭建好解題環(huán)境并梳理從暴力解到最優(yōu)解的思考路徑。2.1 解題環(huán)境準(zhǔn)備對于 LeetCode 刷題一個簡潔高效的本地環(huán)境能極大提升練習(xí)和調(diào)試效率。編程語言Python 3.8。本文所有代碼均基于 Python 3。開發(fā)工具任選其一即可。本地IDEPyCharm, VSCode。建議安裝 Python 插件配置好代碼提示和調(diào)試功能。在線平臺力扣LeetCode官網(wǎng)的代碼編輯器已足夠完成本題。核心思路驗證我們可以在本地創(chuàng)建測試用例來驗證算法的正確性而無需依賴在線判題系統(tǒng)。一個簡單的本地測試腳本結(jié)構(gòu)如下# test_leetcode598.py def maxCount(m, n, ops): # 這里是你的解法函數(shù) pass if __name__ __main__: # 測試用例1 m, n 3, 3 ops [[2,2], [3,3]] print(f測試1: m{m}, n{n}, ops{ops}) print(f預(yù)期輸出: 4) print(f實際輸出: {maxCount(m, n, ops)}) print(- * 20) # 測試用例2: ops為空 m, n 3, 3 ops [] print(f測試2: m{m}, n{n}, ops{ops}) print(f預(yù)期輸出: 9) # 所有元素都是0最大整數(shù)0的個數(shù)是9 print(f實際輸出: {maxCount(m, n, ops)})2.2 從暴力解到數(shù)學(xué)解的思維推導(dǎo)第一步最直觀的暴力解法不可行但有助于理解暴力法的思路是嚴(yán)格按照題目描述模擬初始化一個m x n的全零矩陣。遍歷ops中的每一個操作[a, b]。對于每個操作使用兩層循環(huán)遍歷i從0到a-1j從0到b-1對矩陣對應(yīng)位置加一。遍歷整個矩陣找到最大值并統(tǒng)計其出現(xiàn)次數(shù)。def maxCount_bruteforce(m: int, n: int, ops: List[List[int]]) - int: # 注意此方法在 m, n, k 較大時會超時僅用于理解 import itertools # 初始化矩陣 matrix [[0] * n for _ in range(m)] # 執(zhí)行所有操作 for a, b in ops: for i in range(a): for j in range(b): matrix[i][j] 1 # 找到最大值并計數(shù) max_val 0 count 0 for row in matrix: for val in row: if val max_val: max_val val count 1 elif val max_val: count 1 return count時間復(fù)雜度分析假設(shè)有k個操作每個操作平均影響(a*b)個元素最壞情況下每次操作都覆蓋接近整個矩陣則總操作次數(shù)約為O(k * m * n)。當(dāng)m, n, k達(dá)到10^4時運(yùn)算量是10^12級別必然超時。第二步觀察規(guī)律尋找突破口既然暴力法行不通我們必須觀察規(guī)律?；仡櫴纠僮鱗2,2]影響了第0、1行第0、1列。操作[3,3]影響了第0、1、2行第0、1、2列。最終哪些格子被加了兩次只有那些同時被所有操作覆蓋的格子即行索引在所有操作的a的最小值以內(nèi)且列索引在所有操作的b的最小值以內(nèi)的格子。核心洞察每次操作都是對矩陣左上角的一個矩形區(qū)域進(jìn)行加一。一個格子最終的值等于覆蓋了這個格子的操作的數(shù)量。因此值最大的格子就是被所有操作都覆蓋了的格子。被所有操作覆蓋的格子其行索引必須小于所有a中的最小值min_a列索引必須小于所有b中的最小值min_b。這些格子的數(shù)量就是min_a * min_b。特別地如果操作列表ops為空那么沒有任何操作執(zhí)行所有格子保持為0最大整數(shù)0的個數(shù)就是整個矩陣的大小m * n。第三步得出最優(yōu)解問題瞬間簡化我們不需要矩陣只需要遍歷一次ops數(shù)組找到所有a的最小值和所有b的最小值。最終答案就是min_a * min_b同時需要與m和n取較小值因為操作可能給出比矩陣本身更大的范圍例如a m但實際有效的格子不能超出矩陣邊界。3. 核心算法實現(xiàn)與代碼詳解掌握了數(shù)學(xué)原理后我們來實現(xiàn)最優(yōu)解并詳細(xì)分析代碼的每一個部分。3.1 最優(yōu)解 Python 實現(xiàn)from typing import List class Solution: def maxCount(self, m: int, n: int, ops: List[List[int]]) - int: 計算執(zhí)行所有區(qū)間加法操作后矩陣中最大整數(shù)的個數(shù)。 參數(shù): m (int): 矩陣行數(shù) n (int): 矩陣列數(shù) ops (List[List[int]]): 操作列表每個操作是[a, b] 返回: int: 最大整數(shù)的個數(shù) # 初始化最小行和最小列為矩陣的原始邊界 min_row m min_col n # 遍歷所有操作更新被所有操作共同覆蓋區(qū)域的行列邊界 for a, b in ops: # 取當(dāng)前操作范圍與歷史最小范圍的交集 min_row min(min_row, a) min_col min(min_col, b) # 共同覆蓋區(qū)域的格子數(shù)即為最大整數(shù)的個數(shù) return min_row * min_col代碼行數(shù)非常精簡核心邏輯只有 4 行。3.2 代碼逐行解析與邊界處理初始化 (min_row m,min_col n)為什么初始化為m和n因為矩陣的有效索引范圍是[0, m-1]和[0, n-1]。任何操作的有效a和b都不可能大于m和n大于的部分不影響矩陣。初始化為m和n可以保證在遍歷ops時min函數(shù)能正確取到實際有效的最小值。更重要的是它完美處理了ops為空的情況遍歷不會執(zhí)行min_row和min_col保持為m和n最終返回m * n這正是全為0的矩陣中最大數(shù)0的個數(shù)。遍歷操作 (for a, b in ops:)使用 Python 的迭代解包直接獲取每個操作的a和b。更新最小范圍 (min_row min(min_row, a),min_col min(min_col, b))這是算法的核心。min_row記錄了所有操作中a的最小值即所有操作都覆蓋的最大行索引1。min_col同理。這個交集矩形就是被所有操作“雨露均沾”的區(qū)域。返回結(jié)果 (return min_row * min_col)交集矩形的面積即為被加次數(shù)最多的格子數(shù)量也就是最大整數(shù)的個數(shù)。3.3 復(fù)雜度分析時間復(fù)雜度O(k)其中k是操作列表ops的長度。我們只需要一次線性遍歷。空間復(fù)雜度O(1)只使用了常數(shù)級別的額外變量 (min_row,min_col)。與暴力法的 O(m*n) 空間相比有巨大優(yōu)勢。4. 完整測試與驗證案例理論需要實踐檢驗。下面我們構(gòu)建多個測試案例包括常規(guī)情況、邊界情況和特殊輸入來驗證算法的魯棒性。4.1 基礎(chǔ)功能測試我們將上面的解法嵌入一個完整的測試框架中。# leetcode598_solution.py from typing import List class Solution: def maxCount(self, m: int, n: int, ops: List[List[int]]) - int: min_row, min_col m, n for a, b in ops: min_row min(min_row, a) min_col min(min_col, b) return min_row * min_col def test(): solution Solution() # 測試用例1: 題目示例 assert solution.maxCount(3, 3, [[2,2], [3,3]]) 4 print(測試用例1通過: m3, n3, ops[[2,2],[3,3]] - 4) # 測試用例2: 單個操作 assert solution.maxCount(3, 3, [[1,1]]) 1 print(測試用例2通過: m3, n3, ops[[1,1]] - 1) # 測試用例3: 操作范圍超出矩陣 assert solution.maxCount(2, 2, [[5,5], [3,2]]) 4 # min(5,3,2)2, min(5,2,2)2, 2*24 print(測試用例3通過: m2, n2, ops[[5,5],[3,2]] - 4) # 測試用例4: 無操作 assert solution.maxCount(40000, 40000, []) 40000 * 40000 print(測試用例4通過: m40000, n40000, ops[] - 1600000000) # 測試用例5: 操作a或b為0 (根據(jù)題目描述a和b為正整數(shù)但為防御考慮) # 假設(shè)輸入保證為正整數(shù)此用例僅作思維擴(kuò)展。若a或b為0則該操作不影響任何元素。 # 在算法中min_row或min_col可能被更新為0最終結(jié)果為0。 # assert solution.maxCount(3, 3, [[2,2], [0,3]]) 0 # 假設(shè)允許0輸入 # print(測試用例5通過假設(shè)性) # 測試用例6: 大量操作性能測試模擬 import random, time m, n 40000, 40000 k 10000 # 生成隨機(jī)操作a和b在[1, 40000]之間 random_ops [[random.randint(1, m), random.randint(1, n)] for _ in range(k)] start time.time() result solution.maxCount(m, n, random_ops) end time.time() print(f測試用例6通過: 大規(guī)模數(shù)據(jù) m{m}, n{n}, k{k}, 結(jié)果{result}, 耗時 {end-start:.4f} 秒) print(所有基礎(chǔ)測試用例通過) if __name__ __main__: test()運(yùn)行上述腳本你將看到所有測試用例快速通過尤其是用例6即使面對40000*40000的矩陣規(guī)模和10000次操作也能在毫秒級完成計算充分體現(xiàn)了 O(k) 算法的效率。4.2 與暴力法的結(jié)果對比驗證為了確保我們的優(yōu)化算法結(jié)果正確可以編寫一個函數(shù)在小規(guī)模數(shù)據(jù)上對比暴力解與最優(yōu)解的結(jié)果。def compare_with_bruteforce(m, n, ops): 在小規(guī)模數(shù)據(jù)上對比最優(yōu)解和暴力解用于驗證正確性 def brute_force(m, n, ops): matrix [[0] * n for _ in range(m)] for a, b in ops: for i in range(a): for j in range(b): if i m and j n: # 防止索引越界 matrix[i][j] 1 max_val 0 count 0 for row in matrix: for val in row: if val max_val: max_val val count 1 elif val max_val: count 1 return count sol Solution() optimal_result sol.maxCount(m, n, ops) brute_result brute_force(m, n, ops) if optimal_result brute_result: print(f驗證通過: m{m}, n{n}, ops{ops}) print(f 最優(yōu)解: {optimal_result}, 暴力解: {brute_result}) else: print(f驗證失敗: m{m}, n{n}, ops{ops}) print(f 最優(yōu)解: {optimal_result}, 暴力解: {brute_result}) return optimal_result brute_result # 運(yùn)行一些對比測試 test_cases [ (3, 3, [[2,2], [3,3]]), (5, 5, [[1,5], [5,1], [3,3]]), (2, 2, [[5,5]]), (4, 4, []), ] all_pass all(compare_with_bruteforce(*case) for case in test_cases) print(f\n所有對比測試 {全部通過 if all_pass else 存在失敗})這個對比驗證能給你充分的信心證明數(shù)學(xué)優(yōu)化解法的正確性。5. 算法擴(kuò)展與變式思考掌握了基礎(chǔ)解法后我們可以思考一些相關(guān)的變式問題這有助于深化對區(qū)間操作類問題的理解。5.1 如果操作不是加一而是加一個任意值val呢原題是每次加一。如果操作變?yōu)閇a, b, val]表示對左上角a x b區(qū)域加valval可為正或負(fù)。求最終矩陣的最大值及其個數(shù)。思路分析 此時一個格子最終的值等于所有覆蓋它的操作的val之和。最大值出現(xiàn)的區(qū)域仍然是所有val為正數(shù)的操作共同覆蓋的區(qū)域嗎不一定因為負(fù)數(shù)的val會減少值。問題變得復(fù)雜更像是一個二維差分或二維前綴和的問題。解決方法二維差分這是處理此類“區(qū)間批量增加一個值”的高效方法。遍歷所有操作在差分?jǐn)?shù)組上進(jìn)行標(biāo)記。最后通過計算前綴和得到原矩陣。再遍歷矩陣找最大值和計數(shù)。def maxCount_with_values(m: int, n: int, ops: List[List[int]]) - (int, int): 變式ops中的每個元素是 [a, b, val] 返回最大值最大值的個數(shù) # 初始化差分?jǐn)?shù)組多一圈方便處理邊界 diff [[0] * (n 2) for _ in range(m 2)] for a, b, val in ops: if a m: a m if b n: b n # 二維差分更新公式對左上角(0,0)到右下角(a-1, b-1)的矩形加val diff[1][1] val diff[1][b1] - val diff[a1][1] - val diff[a1][b1] val # 計算前綴和得到原矩陣 matrix [[0] * n for _ in range(m)] max_val float(-inf) count 0 # 利用差分?jǐn)?shù)組恢復(fù)原矩陣并找最大值 for i in range(1, m1): for j in range(1, n1): # 計算前綴和 diff[i][j] diff[i-1][j] diff[i][j-1] - diff[i-1][j-1] current_val diff[i][j] if current_val max_val: max_val current_val count 1 elif current_val max_val: count 1 return max_val, count復(fù)雜度時間復(fù)雜度 O(mn k)空間復(fù)雜度 O(mn)。當(dāng) m, n 很大時可能仍需優(yōu)化但比模擬每個操作要高效得多。5.2 如果操作不是針對左上角而是任意矩形區(qū)域呢原題操作區(qū)域總是從(0,0)開始。如果操作定義為對任意矩形區(qū)域[x1, y1, x2, y2]加一求最大整數(shù)的個數(shù)。思路分析 這變成了一個標(biāo)準(zhǔn)的**二維區(qū)間更新、單點(diǎn)查詢或最終統(tǒng)一查詢**問題。二維差分依然是標(biāo)準(zhǔn)解法。最終最大值的個數(shù)需要在得到整個矩陣后遍歷尋找。5.3 在數(shù)據(jù)庫或?qū)嶋H業(yè)務(wù)中的類比這種“區(qū)間疊加求最大覆蓋”的思想在現(xiàn)實中有很多應(yīng)用用戶權(quán)限系統(tǒng)多個角色對某個功能模塊的權(quán)限進(jìn)行疊加例如可讀、可寫最終用戶的權(quán)限是這些角色的并集或最高級別。尋找擁有“最高權(quán)限”的用戶群可以類比為尋找被所有高權(quán)限角色覆蓋的用戶。廣告投放統(tǒng)計在多個時間段、多個地域投放廣告統(tǒng)計曝光量最大的時段和地域組合。資源調(diào)度多個任務(wù)請求占用某個資源池的不同子區(qū)域?qū)ふ邑?fù)載最重的區(qū)域。理解這類問題的抽象模型能幫助你在遇到實際業(yè)務(wù)問題時快速識別并套用合適的算法。6. 常見錯誤與排查指南即使在理解了最優(yōu)解法后實現(xiàn)時也可能遇到一些陷阱。下面列出常見錯誤及其解決方法。問題現(xiàn)象可能原因解決方案與排查思路返回結(jié)果比預(yù)期小未正確處理ops為空的情況。當(dāng)ops為空時應(yīng)返回m * n。檢查代碼邏輯。最優(yōu)解法中將min_row和min_col初始化為m和n遍歷為空時直接返回m*n這是正確的。如果初始化為float(inf)則需要在遍歷后判斷是否被更新過。返回結(jié)果比預(yù)期大操作中的a或b可能大于m或n。在計算最小范圍時誤用了max函數(shù)。題目保證a和b是正整數(shù)但未明確說明與m, n的關(guān)系。我們的算法中min_row min(min_row, a)是合理的因為a若大于m其有效部分也只是前m行取min會自動將其限制到m。確保你使用的是min而不是max。代碼在 LeetCode 上報語法錯誤Python 版本或函數(shù)簽名問題。LeetCode 使用List需要從typing導(dǎo)入。在代碼開頭添加from typing import List。確保函數(shù)名、參數(shù)名與題目要求一致本題是def maxCount(self, m: int, n: int, ops: List[List[int]]) - int:。本地測試通過提交超時可能錯誤地使用了暴力解法或者最優(yōu)解法中存在低效操作如在循環(huán)中進(jìn)行了不必要的列表創(chuàng)建。確認(rèn)你的算法時間復(fù)雜度是O(k)并且沒有在循環(huán)內(nèi)嵌套其他循環(huán)或調(diào)用高復(fù)雜度函數(shù)。使用我們提供的最優(yōu)解代碼。對于變式問題如加任意值結(jié)果錯誤二維差分的構(gòu)建或前綴和計算公式錯誤。仔細(xì)推導(dǎo)二維差分公式。記住核心四步更新diff[x1][y1] valdiff[x1][y21] - valdiff[x21][y1] - valdiff[x21][y21] val其中(x1,y1)是左上角(x2,y2)是右下角。恢復(fù)原矩陣時prefix[i][j] diff[i][j] prefix[i-1][j] prefix[i][j-1] - prefix[i-1][j-1]調(diào)試建議使用小數(shù)據(jù)測試用題目示例和自定義的簡單案例如m2,n2在本地或力扣的 Playground 運(yùn)行打印中間變量?？梢暬瘜τ诙S矩陣問題可以嘗試手動畫一個 3x3 或 4x4 的網(wǎng)格模擬操作過程驗證你的算法得出的“交集矩形”是否正確。邊界測試務(wù)必測試ops[]ops中包含a0或b0如果允許am,bn等情況。7. 最佳實踐與刷題心得解決這道題的過程是一個典型的算法優(yōu)化案例。從中我們可以總結(jié)出適用于 LeetCode 乃至實際工程問題解決的最佳實踐。7.1 算法優(yōu)化思維模式從暴力法開始思考不要害怕先想出最直觀、可能低效的解法。這是理解問題的第一步也是尋找優(yōu)化線索的基礎(chǔ)。尋找規(guī)律與不變性在暴力模擬的過程中主動觀察數(shù)據(jù)的變化規(guī)律。本題的關(guān)鍵規(guī)律是“最大值的區(qū)域是所有操作范圍的交集”。很多題目都隱藏著類似的“不變量”或“單調(diào)性”。降維打擊當(dāng)數(shù)據(jù)規(guī)模很大時思考能否將問題轉(zhuǎn)化到更低的維度或更簡單的模型。本題將二維的矩陣加操作轉(zhuǎn)化為了對一維邊界a和b求最小值?？紤]極端情況空操作 (ops[])、單個操作、操作范圍極大等情況往往是代碼的“死角”也是面試官喜歡考察的點(diǎn)。7.2 Python 編碼實踐善用內(nèi)置函數(shù)和迭代本題中for a, b in ops:和min()函數(shù)的使用讓代碼非常簡潔。Python 的迭代器和解包能提升代碼可讀性。類型提示雖然 LeetCode 不強(qiáng)制但在本地代碼或大型項目中使用from typing import List, Tuple等類型提示有助于提高代碼可維護(hù)性和 IDE 的智能提示。函數(shù)單一職責(zé)將解題函數(shù)maxCount保持簡潔只負(fù)責(zé)核心邏輯。測試、驗證等輔助功能放在其他函數(shù)或if __name__ __main__:塊中。7.3 針對區(qū)間操作類問題的通用策略“區(qū)間加法 II”屬于“區(qū)間更新”問題家族。遇到類似問題可以按以下策略思考區(qū)間是否固定起點(diǎn)如本題從(0,0)開始可能用找交集的方法。如果是任意區(qū)間優(yōu)先考慮差分?jǐn)?shù)組一維/二維。是否需要動態(tài)查詢?nèi)绻枰诙啻胃碌倪^程中間查詢某個值可能需要更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)如線段樹或樹狀數(shù)組。操作是否可交換本題的加法操作是可交換和可結(jié)合的順序不影響最終結(jié)果。如果操作不可交換如先乘后加則需要記錄操作順序或使用不同的方法。數(shù)據(jù)范圍始終根據(jù)m,n,k的數(shù)據(jù)范圍估算暴力法的復(fù)雜度并判斷是否需要O(log N)或O(1)的優(yōu)化方法。7.4 在面試中如何闡述解題思路如果你在面試中遇到此題可以按照以下結(jié)構(gòu)來溝通澄清問題復(fù)述題目確認(rèn)輸入輸出和邊界條件如ops為空。提出暴力法先給出最直接的模擬思路并分析其時間復(fù)雜度 O(kmn) 和空間復(fù)雜度 O(m*n)指出在大數(shù)據(jù)下不可行。尋找優(yōu)化闡述你觀察到的規(guī)律——“每次操作都是左上角矩形”、“一個格子最終值等于覆蓋它的操作數(shù)”、“因此最大值出現(xiàn)在所有操作的交集矩形中”。給出最優(yōu)解將問題轉(zhuǎn)化為求所有a的最小值和所有b的最小值答案為min_a * min_b。強(qiáng)調(diào)時間復(fù)雜度 O(k)空間復(fù)雜度 O(1)。代碼實現(xiàn)寫出簡潔的代碼。測試用例主動提出測試用例包括常規(guī)示例、空操作、單操作、大范圍操作等。擴(kuò)展討論如果時間允許可以簡要提一下如果操作值不同或區(qū)間任意時的差分?jǐn)?shù)組解法展示知識廣度。通過“區(qū)間加法 II”這道題我們不僅學(xué)會了一個巧妙的優(yōu)化技巧更重要的是訓(xùn)練了從具體操作中抽象出數(shù)學(xué)本質(zhì)的思維能力。這種能力在解決更復(fù)雜的算法問題時至關(guān)重要。建議讀者在理解本題后可以去嘗試 LeetCode 上其他區(qū)間相關(guān)題目如 370. 區(qū)間加法一維差分、1094. 拼車一維差分應(yīng)用、731. 我的日程安排 II差分思想等鞏固和深化對這一類問題的掌握。