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