棧實(shí)戰(zhàn))
1. 力扣高頻算法題深度解析與實(shí)戰(zhàn)指南作為程序員面試的金標(biāo)準(zhǔn)力扣LeetCode算法題一直是技術(shù)人成長(zhǎng)的必經(jīng)之路。今天我將結(jié)合自己刷題500的經(jīng)驗(yàn)深度解析394.字符串解碼、739.每日溫度、84.柱狀圖中最大的矩形這三道高頻題目。這些題目分別來自字符串處理、單調(diào)棧和動(dòng)態(tài)規(guī)劃等核心算法領(lǐng)域在字節(jié)、騰訊等大廠面試中出現(xiàn)率超過60%。2. 394.字符串解碼嵌套字符串的展開藝術(shù)2.1 問題本質(zhì)與核心難點(diǎn)給定一個(gè)類似3[a2[c]]的編碼字符串需要展開為accaccacc。這類嵌套結(jié)構(gòu)天然適合用?；蜻f歸處理難點(diǎn)在于多重嵌套時(shí)的狀態(tài)保存如遇到[“需要暫存當(dāng)前結(jié)果數(shù)字可能有多位不能簡(jiǎn)單用ASCII判斷需要處理字符、數(shù)字、括號(hào)三種元素類型2.2 雙棧解法實(shí)現(xiàn)細(xì)節(jié)def decodeString(s: str) - str: stack [] num_stack [] current_str current_num 0 for char in s: if char.isdigit(): current_num current_num * 10 int(char) elif char [: num_stack.append(current_num) stack.append(current_str) current_str current_num 0 elif char ]: num num_stack.pop() prev_str stack.pop() current_str prev_str num * current_str else: current_str char return current_str關(guān)鍵點(diǎn)遇到[時(shí)當(dāng)前字符串和數(shù)字都要入棧遇到]時(shí)要同時(shí)操作兩個(gè)棧2.3 遞歸解法對(duì)比遞歸版本更簡(jiǎn)潔但可能棧溢出def decodeString(s, i0): res while i len(s) and s[i] ! ]: if not s[i].isdigit(): res s[i] i 1 else: num 0 while i len(s) and s[i].isdigit(): num num * 10 int(s[i]) i 1 i 1 # skip [ inner, i decodeString(s, i) i 1 # skip ] res inner * num return res, i3. 739.每日溫度單調(diào)棧的經(jīng)典應(yīng)用3.1 問題建模給定溫度列表[73,74,75,71,69,72,76]需要返回等待更暖天數(shù)[1,1,4,2,1,1,0]。這本質(zhì)上是找每個(gè)元素右邊第一個(gè)更大數(shù)的距離。3.2 單調(diào)棧實(shí)現(xiàn)模板def dailyTemperatures(T): stack [] res [0] * len(T) for i in range(len(T)): while stack and T[i] T[stack[-1]]: prev stack.pop() res[prev] i - prev stack.append(i) return res技巧棧中存儲(chǔ)的是下標(biāo)而非溫度值這樣既能比較溫度又能計(jì)算天數(shù)差3.3 復(fù)雜度分析與變種時(shí)間復(fù)雜度O(n)每個(gè)元素最多入棧出棧一次空間復(fù)雜度O(n)最壞情況遞減序列全部入棧變種處理價(jià)格跨度、股票波動(dòng)等問題時(shí)同樣適用4. 84.柱狀圖中最大的矩形單調(diào)棧的極致運(yùn)用4.1 暴力解法到最優(yōu)解演進(jìn)暴力枚舉所有左右邊界O(n2)超時(shí)固定高度找最大寬度O(n2)單調(diào)棧優(yōu)化O(n)4.2 單調(diào)棧解法精講def largestRectangleArea(heights): heights [0] heights [0] # 哨兵節(jié)點(diǎn) stack [] max_area 0 for i in range(len(heights)): while stack and heights[i] heights[stack[-1]]: h heights[stack.pop()] w i - stack[-1] - 1 max_area max(max_area, h * w) stack.append(i) return max_area注意事項(xiàng)首尾添加哨兵節(jié)點(diǎn)避免邊界判斷寬度計(jì)算是當(dāng)前i與棧頂下一位的差減一出棧時(shí)才計(jì)算面積4.3 可視化理解以[2,1,5,6,2,3]為例遇到1時(shí)2出棧計(jì)算2×12遇到2時(shí)6和5相繼出棧6的面積6×(4-2-1)65的面積5×(4-1-1)10最終最大面積為105. 刷題方法論與面試技巧5.1 同類題目歸納字符串解碼類似385.迷你語法分析器、1087.花括號(hào)展開單調(diào)棧系列42.接雨水、907.子數(shù)組的最小值之和柱狀圖變種85.最大矩形、221.最大正方形5.2 面試實(shí)戰(zhàn)建議先明確問題邊界詢問面試官?gòu)谋┝夥ㄕf起逐步優(yōu)化手寫代碼時(shí)注意變量命名用測(cè)試用例驗(yàn)證如空輸入、極端情況5.3 調(diào)試技巧字符串解碼打印每次入棧出棧狀態(tài)單調(diào)棧問題可視化繪制元素進(jìn)出棧過程柱狀圖面積在紙上畫出每個(gè)步驟的計(jì)算方式這三道題涵蓋了算法面試中最關(guān)鍵的棧應(yīng)用場(chǎng)景。建議在理解的基礎(chǔ)上每個(gè)類型至少練習(xí)5道相似題目。我在準(zhǔn)備面試時(shí)會(huì)專門建立錯(cuò)題本記錄這類問題的變形和解法規(guī)律。比如發(fā)現(xiàn)很多單調(diào)棧問題都可以通過添加哨兵節(jié)點(diǎn)來簡(jiǎn)化代碼這就是刷題量積累后的模式識(shí)別能力。 力扣高頻算法題解析：字符串解碼與單調(diào)棧實(shí)戰(zhàn)
1. 力扣高頻算法題深度解析與實(shí)戰(zhàn)指南作為程序員面試的金標(biāo)準(zhǔn)力扣LeetCode算法題一直是技術(shù)人成長(zhǎng)的必經(jīng)之路。今天我將結(jié)合自己刷題500的經(jīng)驗(yàn)深度解析394.字符串解碼、739.每日溫度、84.柱狀圖中最大的矩形這三道高頻題目。這些題目分別來自字符串處理、單調(diào)棧和動(dòng)態(tài)規(guī)劃等核心算法領(lǐng)域在字節(jié)、騰訊等大廠面試中出現(xiàn)率超過60%。2. 394.字符串解碼嵌套字符串的展開藝術(shù)2.1 問題本質(zhì)與核心難點(diǎn)給定一個(gè)類似3[a2[c]]的編碼字符串需要展開為accaccacc。這類嵌套結(jié)構(gòu)天然適合用?；蜻f歸處理難點(diǎn)在于多重嵌套時(shí)的狀態(tài)保存如遇到[“需要暫存當(dāng)前結(jié)果數(shù)字可能有多位不能簡(jiǎn)單用ASCII判斷需要處理字符、數(shù)字、括號(hào)三種元素類型2.2 雙棧解法實(shí)現(xiàn)細(xì)節(jié)def decodeString(s: str) - str: stack [] num_stack [] current_str current_num 0 for char in s: if char.isdigit(): current_num current_num * 10 int(char) elif char [: num_stack.append(current_num) stack.append(current_str) current_str current_num 0 elif char ]: num num_stack.pop() prev_str stack.pop() current_str prev_str num * current_str else: current_str char return current_str關(guān)鍵點(diǎn)遇到[時(shí)當(dāng)前字符串和數(shù)字都要入棧遇到]時(shí)要同時(shí)操作兩個(gè)棧2.3 遞歸解法對(duì)比遞歸版本更簡(jiǎn)潔但可能棧溢出def decodeString(s, i0): res while i len(s) and s[i] ! ]: if not s[i].isdigit(): res s[i] i 1 else: num 0 while i len(s) and s[i].isdigit(): num num * 10 int(s[i]) i 1 i 1 # skip [ inner, i decodeString(s, i) i 1 # skip ] res inner * num return res, i3. 739.每日溫度單調(diào)棧的經(jīng)典應(yīng)用3.1 問題建模給定溫度列表[73,74,75,71,69,72,76]需要返回等待更暖天數(shù)[1,1,4,2,1,1,0]。這本質(zhì)上是找每個(gè)元素右邊第一個(gè)更大數(shù)的距離。3.2 單調(diào)棧實(shí)現(xiàn)模板def dailyTemperatures(T): stack [] res [0] * len(T) for i in range(len(T)): while stack and T[i] T[stack[-1]]: prev stack.pop() res[prev] i - prev stack.append(i) return res技巧棧中存儲(chǔ)的是下標(biāo)而非溫度值這樣既能比較溫度又能計(jì)算天數(shù)差3.3 復(fù)雜度分析與變種時(shí)間復(fù)雜度O(n)每個(gè)元素最多入棧出棧一次空間復(fù)雜度O(n)最壞情況遞減序列全部入棧變種處理價(jià)格跨度、股票波動(dòng)等問題時(shí)同樣適用4. 84.柱狀圖中最大的矩形單調(diào)棧的極致運(yùn)用4.1 暴力解法到最優(yōu)解演進(jìn)暴力枚舉所有左右邊界O(n2)超時(shí)固定高度找最大寬度O(n2)單調(diào)棧優(yōu)化O(n)4.2 單調(diào)棧解法精講def largestRectangleArea(heights): heights [0] heights [0] # 哨兵節(jié)點(diǎn) stack [] max_area 0 for i in range(len(heights)): while stack and heights[i] heights[stack[-1]]: h heights[stack.pop()] w i - stack[-1] - 1 max_area max(max_area, h * w) stack.append(i) return max_area注意事項(xiàng)首尾添加哨兵節(jié)點(diǎn)避免邊界判斷寬度計(jì)算是當(dāng)前i與棧頂下一位的差減一出棧時(shí)才計(jì)算面積4.3 可視化理解以[2,1,5,6,2,3]為例遇到1時(shí)2出棧計(jì)算2×12遇到2時(shí)6和5相繼出棧6的面積6×(4-2-1)65的面積5×(4-1-1)10最終最大面積為105. 刷題方法論與面試技巧5.1 同類題目歸納字符串解碼類似385.迷你語法分析器、1087.花括號(hào)展開單調(diào)棧系列42.接雨水、907.子數(shù)組的最小值之和柱狀圖變種85.最大矩形、221.最大正方形5.2 面試實(shí)戰(zhàn)建議先明確問題邊界詢問面試官?gòu)谋┝夥ㄕf起逐步優(yōu)化手寫代碼時(shí)注意變量命名用測(cè)試用例驗(yàn)證如空輸入、極端情況5.3 調(diào)試技巧字符串解碼打印每次入棧出棧狀態(tài)單調(diào)棧問題可視化繪制元素進(jìn)出棧過程柱狀圖面積在紙上畫出每個(gè)步驟的計(jì)算方式這三道題涵蓋了算法面試中最關(guān)鍵的棧應(yīng)用場(chǎng)景。建議在理解的基礎(chǔ)上每個(gè)類型至少練習(xí)5道相似題目。我在準(zhǔn)備面試時(shí)會(huì)專門建立錯(cuò)題本記錄這類問題的變形和解法規(guī)律。比如發(fā)現(xiàn)很多單調(diào)棧問題都可以通過添加哨兵節(jié)點(diǎn)來簡(jiǎn)化代碼這就是刷題量積累后的模式識(shí)別能力。