EX:
[0,1,0,2,1,0,1,3,2,1,2,1]
黑色 bar 的高度對應到array個項的值，藍色的部份表示由這些bar形成的空間可以留住的水。
以這個例子來說可以留住的水就是6個單位。
想法:
這題還真的蠻難的，一開始我只想得到O(n^2)的暴力法，主要想法就是從頭遍歷array，在每個index的時候分別往左跟往右去找兩邊最高的bar，然後該index與其他bar可以留住的水量就是 min(left_max, right_max) - height(當位置的高)，如果大於零就更新留住的水量。
後來才發現這題有多種 O(n) 的解法，都還蠻巧妙的。
1. DP solution: O(n) time O(n) space
DP 主要的概念就是空間換取時間，我們上述的暴力法會需要O(n^2)的時間主要原因在於在每個位置時我都必須要向左和向又搜尋才能知道對當前位置來說左右最大的bar是誰，而這邊DP的作法就是基於這點做改良，在實際計算能留住多少水之前，先分別從左往右與從右往左遍歷一遍array，從左往右時可以紀錄對每個位置來說left_max是多少，從右往左可以紀錄right_max，因此需要額外的兩個array來分別紀錄每個位置的left_max與right_max，因此為O(n) time, O(n) space。
2. Monotonic Stack solution: O(n) time O(n) space
單調棧 (Monotonic stack)的技巧在 84. Largest Rectangle in Histogram 中也有使用到，通常單調棧的作法對我來說都是比較不直覺的。因為要能夠形成凹地收集雨水必定是中間低兩端高，所以我們維護一個"遞減"的單調棧只要當前元素比 stack.top 還要大就表示兩者之間可能形成窪地，且當前元素就是窪地的右邊界，而 stack.top 的前一個元素就是窪地的左邊界，之後只要利用左右邊界較低的那邊當做 height 就可以計算出可以留住的水量。
3. Two pointer solution: O(n) time O(1) space
這個作法還蠻巧妙的，可以達到O(n) time 同時 O(1) 不需要額外空間！，主要概念就是同時從左到右且從右到左遍歷，每次比較當前的left位置與right位置bar的大小，因為能留住多少水是由高度較矮的bar所決定的，因此每次選擇bar較矮的一邊前進，同時判斷在該bar之前是否有比它更高的bar(左邊的之前就是看它左邊,右邊的之前就是看它右邊)，若有則表示在該bar那格上可以留住left_max/right_max - height[current_bar]的水(這邊比較需要想一下，因為每次都是較矮的一邊前進，所以可以確保另一邊目前的max一定是大於該bar的高度與該bar前面的bar,因此保證可以留住水)，若在該bar之前沒有比它更高的bar則更新該bar高度為目前的left_max/right_max。(不懂的話過一遍例子就懂了!!!)
總結來說我覺得O(n)的方法裡面還是 DP的作法比較直覺一點也最好理解，畢竟是基於暴力法做改良。
完整程式碼:
解法一(brute-force):
class Solution {
public:
int trap(vector<int>& height) {
int traps = 0;
for (int i = 0; i < height.size(); i++) {
int left_max = 0;
int right_max = 0;
for (int j = i - 1; j >= 0; j--) {
left_max = max(left_max, height[j]);
}
for (int j = i + 1; j < height.size(); j++) {
right_max = max(right_max, height[j]);
}
int traped = min(left_max, right_max) - height[i];
traps = (traped > 0)? traps + traped : traps;
}
return traps;
}
};
解法二(DP ):
class Solution {
public:
int trap(vector<int>& height) {
int traps = 0;
vector<int> max_left(height.size(), 0);
vector<int> max_right(height.size(), 0);
for (int i = 1; i < height.size(); i++) {
max_left[i] = max(height[i-1], max_left[i-1]);
}
for (int i = height.size()-2; i >= 0; i--) {
max_right[i] = max(height[i+1], max_right[i+1]);
}
for (int i = 0; i < height.size(); i++) {
int traped = min(max_left[i], max_right[i]) - height[i];
traps = (traped > 0)? traps + traped : traps;
}
return traps;
}
};
解法三(Monotonic Stack) :
class Solution {
public:
int trap(vector<int>& height) {
stack<int> s;
int cur = 0;
int ans = 0;
while (cur < height.size()) {
// may have left bound and have trap
while (!s.empty() && height[cur] > height[s.top()]) {
auto top = s.top();
s.pop();
// don't have left bound
if (s.empty()) {
break;
}
// horizontal length
auto dis = cur - s.top() - 1;
// trapped depth
auto h_diff = min(height[cur], height[s.top()])-height[top];
ans += dis * h_diff;
}
s.push(cur++);
}
return ans;
}
};
解法四(Two Pointers):
class Solution {
public:
int trap(vector<int>& height) {
int left = 0;
int right = height.size() - 1;
int left_max = 0;
int right_max = 0;
int ans = 0;
while (left < right) {
// bounded by max left
if (height[left] < height[right]) {
if (height[left] > left_max) {
left_max = height[left];
}
// 左邊有比它高的才會進行更新
else {
ans += left_max - height[left];
}
left++;
}
// bounded by max right
else {
if (height[right] > right_max) {
right_max = height[right];
}
// 右邊有比它高的才會進行更新
else {
ans += right_max - height[right];
}
right--;
}
}
return ans;
}
};
沒有留言:
張貼留言