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