此專欄文章是對力扣上演算法題目各種方法的總結和歸納, 整理出最重要的思路和知識重點并以思維導圖形式呈現, 當然也會加上我對導圖的詳解.
目的是為了更方便快捷的記憶和回憶演算法重點(不用每次都重復看題解), 畢竟演算法不是做了一遍就能完全記住的. 所以本文適合已經知道解題思路和方法, 想進一步加強理解和記憶的朋友, 并不適合第一次接觸此題的朋友(可以根據題號先去力扣看看官方題解, 然后再看本文內容).
關于本專欄所有題目的目錄鏈接, 刷演算法題目的順序/注意點/技巧, 以及思維導圖源檔案問題請點擊此鏈接.
想進大廠, 刷演算法是必不可少的, 歡迎和博主一起打卡刷力扣演算法, 博主同步更新了演算法視頻講解 和 其他文章/導圖講解, 更易于理解, 歡迎來看!
文章目錄
- 0.導圖整理
- 1.了解常規思想
- 2.動態規劃 優化時間復雜度
- 3.雙指標 優化空間復雜度
- 4.單調堆疊的思想
- 原始碼
- Python:
- java:
題目鏈接: https://leetcode-cn.com/problems/trapping-rain-water/solution/si-wei-dao-tu-zheng-li-4chong-fang-fa-xi-4uua/
0.導圖整理
1.了解常規思想
對于本題而言, 首先要掌握最常規的思想, 因為下面的一系列方法大多都是在常規思想上進行的各種優化操作.
但其實本題的常規思想也不是那么容易想的, 看到那分布極不規則的接雨水情況, 對于怎么樣將它們求和也并非一樣容易的事.
常規思想中最重要的就是 接水量的計算方法 了, 我們采用對于每個下標 i, 分別計算它能夠接到的水量, 最后將它們相加在一起.
接下來就是每個下標 i 接水量的計算程序了, 從圖中我們可以看出, 一個位置要想接到雨水, 那么兩邊必然要有比它更高的柱子, 并且下雨后水能到達的最大高度等于下標 i 兩邊的最大高度的最小值, 而下標 i 處能接的雨水量等于下標 i 處的水能到達的最大高度減去 height[i].
這就是最重要的接水量的計算程序了, 明白了這個原理之后, 我們只需要分別向左和向右掃描并記錄左邊和右邊的最大高度, 然后計算每個下標位置能接的雨水量.
這就是常規思想的全部思路了, 這個方法會用到兩次回圈, 時間復雜度就達到了 O ( n 2 ) O(n^2) O(n2), 接下來就是我們的優化程序了.
2.動態規劃 優化時間復雜度
上述做法的時間復雜度較高是因為需要對每個下標位置都向兩邊掃描，如果已經知道每個位置兩邊的最大高度, 則可以在 O(n) 的時間內得到能接的雨水總量. 所以我們可以用動態規劃的方法提前得到 每個位置兩邊的最大高度.
明白動態規劃的作用之后, 其實動態規劃規劃的思想還是挺好理解的, 就是下面的經典的四個步驟. 動態規劃最困難的地方在于 推匯出遞推公式, 但本題的遞推公式還是比較容易推導的. 關于動態規劃, 是個重中之重, 以后會專門寫一個專題詳解動態規劃的.
一般來說, 動態規劃的題目在遍歷結束之后就能得到結果了, 但是本題還是需要對動態規劃的結果進行進一步的處理才能得到最終的結果.
在得到陣列 leftMax 和 rightMax 的每個元素值之后, 對于0≤i<n, 下標i處能接的雨水量等于min(leftMax[i],rightMax[i])?height[i]，遍歷每個下標位置即可得到能接的雨水總量.
最后總結了四個注意點, 其中三個是Python的語法問題, 和java還是有挺大差別的, 大家注意一下:
3.雙指標 優化空間復雜度
上面的動態規劃方法雖然將時間復雜度優化到了O(n), 但同時也將空間復雜度由O(1)提升到了O(n), 典型的犧牲空間換取時間的做法, 接下來我們就使用雙指標在保證時間復雜度不變的情況下, 將空間復雜度優化到O(1).
我們先來分析兩個思想最大的不同之處. 由上面動態規劃的圖可以看出, 它對于每個位置都找到了兩邊的最大值, 但實際上, 接的水量是由兩者中的較小值決定的, 所以只要找到較少的那個即可, 沒必要找到較大的那個的最大值, 這就是我們能夠使用雙指標進行優化的原因, 可能比較難理解, 大家多思考一下.
同時h[left] < h[right] 的情況只會出現在：right 剛剛找到自己目前的最大值, left在尋找更大值的程序中， 所以此時必然有leftMax < rightMax, 這樣就滿足了我們尋找兩者中較小者的要求.
明白了雙指標思想優化的地方之后, 我們再來看雙指標的思想就比較容易理解了.
在代碼中有個小的注意點就是 左右指標最終并不需要相等, 滿足小于的條件就可以了, 因為相等時, 表示它們同時指向最大值, 但是在最高點是不會有雨水的.
4.單調堆疊的思想
這個方法和上面幾個就沒太大關系了, 但也是一種很重要的演算法, 也是有很多的應用場景的, 我們來了解下這個演算法的思想.
從名字也可以看出, 它最大的特點就是單調, 也就是堆疊中的元素要么遞增, 要么遞降, 如果有新的元素不滿足這個特點, 就不斷的將堆疊頂元素出堆疊, 直到滿足為止, 這就是它最重要的思想.
本題設計的是一個單調遞減堆疊: 維護一個單調堆疊, 單調堆疊存盤的是下標, 滿足從堆疊底到堆疊頂的下標對應的陣列 height 中的元素遞減.
我們來分析下單調堆疊為什么可以滿足此題的要求. 首先明確一點: 只有產生凹陷的地方才能存盤雨水, 那么高度一定是先減后增, 所以當我們遍歷到 增 這個位置的時候, 前面的減的地方(凹陷處)一定會存盤雨水, 所以我們就將凹陷處出堆疊, 來計算它所能存盤的雨水量.
用演算法思想來表述就是: 從左到右遍歷陣列, 遍歷到下標 i 時, 如果堆疊內至少有兩個元素, 記堆疊頂元素為top, top 的下面一個元素是 left, 則一定有height[left]≥height[top]，如果height[i]>height[top], 則得到一個可以接雨水的區域.
接下來就是雨水量的計算了, 這里有個很大的區別, 之前的方法都是對于單獨的 i 位置進行計算的, 但是單調堆疊在計算的時候是一個長方形的區域, 是按照長度為1,2,3,4分別來求的, 這是最大的不同點, 理解可能有點困難, 我會在視頻中詳解的.
該區域的寬度是i?left?1, 高度是min(height[left],height[i])?height[top], 根據寬度和高度即可計算得到該區域能接的雨水量.
演算法運行的整個程序如下:
在代碼中有兩個要注意的點: 一個是 彈出堆疊頂后判斷堆疊是否為空, 因為當堆疊為空, 說明左邊不存在最大值, 是無法接雨水的.
另一點就是在Python中一般都是利用串列來實作堆疊的, 并沒有使用單獨的資料結構, 所以在操作上和真正的堆疊是有點不同的, 具體操作如下:
原始碼
Python:
# 動態規劃
class Solution:
def trap(self, height: List[int]) -> int:
if not height:
return 0
n = len(height)
leftMax = [height[0]] + [0] * (n - 1) # 簡化的連續賦值
# 正向遍歷陣列 height 得到陣列 leftMax 的每個元素值
for i in range(1, n):
leftMax[i] = max(leftMax[i - 1], height[i])
# 反向遍歷陣列 height 得到陣列 rightMax 的每個元素值
rightMax = [0] * (n - 1) + [height[n - 1]]
for i in range(n - 2, -1, -1): # 逆序遍歷
rightMax[i] = max(rightMax[i + 1], height[i])
# 遍歷每個下標位置即可得到能接的雨水總量
ans = sum(min(leftMax[i], rightMax[i]) - height[i] for i in range(n))
return ans
# 雙指標
class Solution:
def trap(self, height: List[int]) -> int:
ans = 0
left, right = 0, len(height) - 1
leftMax = rightMax = 0
# 不需要相等,相等時,同時指向最大值,在最高點不會有雨水的
while left < right:
leftMax = max(leftMax, height[left])
rightMax = max(rightMax, height[right])
if height[left] < height[right]:
ans += leftMax - height[left]
left += 1
else:
ans += rightMax - height[right]
right -= 1
return ans
# 單調堆疊
class Solution:
def trap(self, height: List[int]) -> int:
ans = 0
stack = list() # 用串列來模擬實作堆疊
n = len(height)
for i, h in enumerate(height): # 同時獲取下標和對應的高度
# height[i] > height[stack[-1]]得到一個可以接雨水的區域
while stack and h > height[stack[-1]]:
top = stack.pop()
if not stack: # 堆疊為空,左邊不存在最大值,無法接雨水
break
left = stack[-1] # left成為新的堆疊頂元素
currWidth = i - left - 1 # 獲取接雨水區域的寬度
currHeight = min(height[left], height[i]) - height[top]
ans += currWidth * currHeight
stack.append(i) # 在對下標i處計算能接的雨水量之后,將i入堆疊,繼續遍歷后面的下標
return ans
java:
# 常規思想
class Solution {
public int trap(int[] height) {
int ans = 0;
int size = height.length;
for (int i = 1; i < size - 1; i++) {
int max_left = 0, max_right = 0;
for (int j = i; j >= 0; j--) { // 向左掃描記錄左邊最大值
max_left = Math.max(max_left, height[j]);
}
for (int j = i; j < size; j++) { // 向右掃描記錄右邊最大值
max_right = Math.max(max_right, height[j]);
} // 下標i處能接到的水量
ans += Math.min(max_left, max_right) - height[i];
}
return ans;
}
}
# 動態規劃
class Solution {
public int trap(int[] height) {
int n = height.length;
if (n == 0) {
return 0;
}
// 正向遍歷陣列 height 得到陣列 leftMax 的每個元素值
int[] leftMax = new int[n];
leftMax[0] = height[0];
for (int i = 1; i < n; ++i) {
leftMax[i] = Math.max(leftMax[i - 1], height[i]);
}
// 反向遍歷陣列 height 得到陣列 rightMax 的每個元素值
int[] rightMax = new int[n];
rightMax[n - 1] = height[n - 1];
for (int i = n - 2; i >= 0; --i) {
rightMax[i] = Math.max(rightMax[i + 1], height[i]);
}
// 遍歷每個下標位置即可得到能接的雨水總量
int ans = 0;
for (int i = 0; i < n; ++i) {
ans += Math.min(leftMax[i], rightMax[i]) - height[i];
}
return ans;
}
}
# 雙指標
class Solution {
public int trap(int[] height) {
int ans = 0;
int left = 0, right = height.length - 1;
int leftMax = 0, rightMax = 0;
// 不需要相等,相等時,同時指向最大值,在最高點不會有雨水的
while (left < right) {
leftMax = Math.max(leftMax, height[left]);
rightMax = Math.max(rightMax, height[right]);
if (height[left] < height[right]) {
ans += leftMax - height[left];
++left;
} else {
ans += rightMax - height[right];
--right;
}
}
return ans;
}
}
# 單調堆疊
class Solution {
public int trap(int[] height) {
int ans = 0;
Deque<Integer> stack = new LinkedList<Integer>();
int n = height.length;
for (int i = 0; i < n; ++i) {
// height[i] > height[stack.peek()]得到一個可以接雨水的區域
while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
int top = stack.pop(); // 獲得接雨水位置的下標
if (stack.isEmpty()) { // 堆疊為空,左邊不存在最大值,無法接雨水
break;
}
int left = stack.peek(); // left成為新的堆疊頂元素
int currWidth = i - left - 1; // 獲取接雨水區域的寬度
int currHeight = Math.min(height[left], height[i]) - height[top];
ans += currWidth * currHeight;
}
stack.push(i); // 在對下標i處計算能接的雨水量之后,將i入堆疊,繼續遍歷后面的下標
}
return ans;
}
}
我的更多精彩文章鏈接, 歡迎查看
各種電腦/軟體/生活/音樂/動漫/電影技巧匯總(你肯定能夠找到你需要的使用技巧)
力扣演算法刷題 根據思維導圖整理筆記快速記憶演算法重點內容(歡迎和博主一起打卡刷題哦)
計算機專業知識 思維導圖整理
最值得收藏的 Python 全部知識點思維導圖整理, 附帶常用代碼/方法/庫/資料結構/常見錯誤/經典思想(持續更新中)
最值得收藏的 C++ 全部知識點思維導圖整理(清華大學鄭莉版), 東南大學軟體工程初試906科目
最值得收藏的 計算機網路 全部知識點思維導圖整理(王道考研), 附帶經典5層結構中英對照和框架簡介
最值得收藏的 演算法分析與設計 全部知識點思維導圖整理(北大慕課課程)
最值得收藏的 資料結構 全部知識點思維導圖整理(王道考研), 附帶經典題型整理
最值得收藏的 人工智能導論 全部知識點思維導圖整理(王萬良慕課課程)
最值得收藏的 數值分析 全部知識點思維導圖整理(東北大學慕課課程)
最值得收藏的 數字影像處理 全部知識點思維導圖整理(武漢大學慕課課程)
紅黑樹 一張導圖解決紅黑樹全部插入和洗掉問題 包含詳細操作原理 情況對比
各種常見排序演算法的時間/空間復雜度 是否穩定 演算法選取的情況 改進 思維導圖整理
人工智能課件 演算法分析課件 Python課件 數值分析課件 機器學習課件 影像處理課件
考研相關科目 知識點 思維導圖整理
考研經驗–東南大學軟體學院軟體工程(這些基礎課和專業課的各種坑和復習技巧你應該知道)
東南大學 軟體工程 906 資料結構 C++ 歷年真題 思維導圖整理
東南大學 軟體工程 復試3門科目歷年真題 思維導圖整理
最值得收藏的 考研高等數學 全部知識點思維導圖整理(張宇, 湯家鳳), 附做題技巧/易錯點/知識點整理
最值得收藏的 考研線性代數 全部知識點思維導圖整理(張宇, 湯家鳳), 附帶慣用思維/做題技巧/易錯點整理
高等數學 中值定理 一張思維導圖解決中值定理所有題型
考研思修 知識點 做題技巧 同類比較 重要會議 1800易錯題 思維導圖整理
考研近代史 知識點 做題技巧 同類比較 重要會議 1800易錯題 思維導圖整理
考研馬原 知識點 做題技巧 同類比較 重要會議 1800易錯題 思維導圖整理
考研數學課程筆記 考研英語課程筆記 考研英語單詞詞根詞綴記憶 考研政治課程筆記
Python相關技術 知識點 思維導圖整理
Numpy常見用法全部OneNote筆記 全部筆記思維導圖整理
Pandas常見用法全部OneNote筆記 全部筆記思維導圖整理
Matplotlib常見用法全部OneNote筆記 全部筆記思維導圖整理
PyTorch常見用法全部OneNote筆記 全部筆記思維導圖整理
Scikit-Learn常見用法全部OneNote筆記 全部筆記思維導圖整理
Java相關技術/ssm框架全部筆記
Spring springmvc Mybatis jsp
科技相關 小米手機
小米 紅米 歷代手機型號大全 發布時間 發布價格
常見手機品牌的各種系列劃分及其特點
歷代CPU和GPU的性能情況和常見后綴的含義 思維導圖整理
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/301273.html
標籤：java