C++實現LeetCode(42.收集雨水)
[LeetCode] 42. Trapping Rain Water 收集雨水
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!
Example:
Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
這道收集雨水的題跟之前的那道 Largest Rectangle in Histogram 有些類似，但是又不太一樣，先來看一種方法，這種方法是基于動態(tài)規(guī)劃 Dynamic Programming 的，維護一個一維的 dp 數組，這個 DP 算法需要遍歷兩遍數組，第一遍在 dp[i] 中存入i位置左邊的最大值，然后開始第二遍遍歷數組，第二次遍歷時找右邊最大值，然后和左邊最大值比較取其中的較小值，然后跟當前值 A[i] 相比，如果大于當前值，則將差值存入結果，參見代碼如下：
C++ 解法一：
class Solution {
public:
int trap(vector<int>& height) {
int res = 0, mx = 0, n = height.size();
vector<int> dp(n, 0);
for (int i = 0; i < n; ++i) {
dp[i] = mx;
mx = max(mx, height[i]);
}
mx = 0;
for (int i = n - 1; i >= 0; --i) {
dp[i] = min(dp[i], mx);
mx = max(mx, height[i]);
if (dp[i] > height[i]) res += dp[i] - height[i];
}
return res;
}
};
Java 解法一：
public class Solution {
public int trap(int[] height) {
int res = 0, mx = 0, n = height.length;
int[] dp = new int[n];
for (int i = 0; i < n; ++i) {
dp[i] = mx;
mx = Math.max(mx, height[i]);
}
mx = 0;
for (int i = n - 1; i >= 0; --i) {
dp[i] = Math.min(dp[i], mx);
mx = Math.max(mx, height[i]);
if (dp[i] - height[i] > 0) res += dp[i] - height[i];
}
return res;
}
}
再看一種只需要遍歷一次即可的解法，這個算法需要 left 和 right 兩個指針分別指向數組的首尾位置，從兩邊向中間掃描，在當前兩指針確定的范圍內，先比較兩頭找出較小值，如果較小值是 left 指向的值，則從左向右掃描，如果較小值是 right 指向的值，則從右向左掃描，若遇到的值比當較小值小，則將差值存入結果，如遇到的值大，則重新確定新的窗口范圍，以此類推直至 left 和 right 指針重合，參見代碼如下：
C++ 解法二：
class Solution {
public:
int trap(vector<int>& height) {
int res = 0, l = 0, r = height.size() - 1;
while (l < r) {
int mn = min(height[l], height[r]);
if (mn == height[l]) {
++l;
while (l < r && height[l] < mn) {
res += mn - height[l++];
}
} else {
--r;
while (l < r && height[r] < mn) {
res += mn - height[r--];
}
}
}
return res;
}
};
Java 解法二：
public class Solution {
public int trap(int[] height) {
int res = 0, l = 0, r = height.length - 1;
while (l < r) {
int mn = Math.min(height[l], height[r]);
if (height[l] == mn) {
++l;
while (l < r && height[l] < mn) {
res += mn - height[l++];
}
} else {
--r;
while (l < r && height[r] < mn) {
res += mn - height[r--];
}
}
}
return res;
}
}
我們可以對上面的解法進行進一步優(yōu)化，使其更加簡潔：
C++ 解法三：
class Solution {
public:
int trap(vector<int>& height) {
int l = 0, r = height.size() - 1, level = 0, res = 0;
while (l < r) {
int lower = height[(height[l] < height[r]) ? l++ : r--];
level = max(level, lower);
res += level - lower;
}
return res;
}
};
Java 解法三：
public class Solution {
public int trap(int[] height) {
int l = 0, r = height.length - 1, level = 0, res = 0;
while (l < r) {
int lower = height[(height[l] < height[r]) ? l++ : r--];
level = Math.max(level, lower);
res += level - lower;
}
return res;
}
}
下面這種解法是用 stack 來做的，博主一開始都沒有注意到這道題的 tag 還有 stack，所以以后在總結的時候還是要多多留意一下標簽啊。其實用 stack 的方法博主感覺更容易理解，思路是，遍歷高度，如果此時棧為空，或者當前高度小于等于棧頂高度，則把當前高度的坐標壓入棧，注意這里不直接把高度壓入棧，而是把坐標壓入棧，這樣方便在后來算水平距離。當遇到比棧頂高度大的時候，就說明有可能會有坑存在，可以裝雨水。此時棧里至少有一個高度，如果只有一個的話，那么不能形成坑，直接跳過，如果多余一個的話，那么此時把棧頂元素取出來當作坑，新的棧頂元素就是左邊界，當前高度是右邊界，只要取二者較小的，減去坑的高度，長度就是右邊界坐標減去左邊界坐標再減1，二者相乘就是盛水量啦，參見代碼如下：
C++ 解法四：
class Solution {
public:
int trap(vector<int>& height) {
stack<int> st;
int i = 0, res = 0, n = height.size();
while (i < n) {
if (st.empty() || height[i] <= height[st.top()]) {
st.push(i++);
} else {
int t = st.top(); st.pop();
if (st.empty()) continue;
res += (min(height[i], height[st.top()]) - height[t]) * (i - st.top() - 1);
}
}
return res;
}
};
Java 解法四：
class Solution {
public int trap(int[] height) {
Stack<Integer> s = new Stack<Integer>();
int i = 0, n = height.length, res = 0;
while (i < n) {
if (s.isEmpty() || height[i] <= height[s.peek()]) {
s.push(i++);
} else {
int t = s.pop();
if (s.isEmpty()) continue;
res += (Math.min(height[i], height[s.peek()]) - height[t]) * (i - s.peek() - 1);
}
}
return res;
}
}
到此這篇關于C++實現LeetCode(42.收集雨水)的文章就介紹到這了,更多相關C++實現收集雨水內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要介紹了C++實現藍橋杯競賽題目---搭積木,本篇文章通過題目分析列舉公式進行分析算法,包含詳細的圖文,以下就是詳細內容,需要的朋友可以參考下2021-07-07
這篇文章主要介紹了C語言之通訊錄的模擬實現代碼,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-04-04
這篇文章主要介紹了C++繼承中的訪問控制,是面向對象程序設計中非常重要的知識點,需要的朋友可以參考下2014-08-08
本文主要介紹了VS2022 Git提交代碼的實現，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2022-05-05
互斥量是一種同步原語,是一種線程同步的手段,用來保護多線程同時訪問的共享數據,本文主要介紹了C++11互斥量的具體使用,感興趣的可以了解一下2023-11-11
本篇文章是對C++中的virtual繼承進行了詳細的分析介紹，需要的朋友參考下2013-05-05
在C語言的程序中包括各種以符號#開頭的編譯指令，這些指令稱為預處理命令。預處理命令屬于C語言編譯器，而不是C語言的組成部分，通過預處理命令可擴展C語言程序設計的環(huán)境2022-05-05
這篇文章主要介紹了c++ 隊列相關知識總結，幫助大家更好的理解和學習使用c++，感興趣的朋友可以了解下2021-03-03
JSON文件無論是在web開發(fā)、客戶端開發(fā)、服務端等開發(fā)中都是應用比較廣泛的的第一種輕量級數據交換格式,非常方便閱讀和編寫,下面這篇文章主要給大家介紹了關于C/C++讀寫JSON數據的詳細過程,需要的朋友可以參考下2023-04-04
這篇文章主要為大家詳細介紹了C++求最大公約數四種方法，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-09-09