繼續慢慢推grind75==
42. 陷阱水
雖然是hard可是感覺蠻簡單ㄉ==
老題目比較單純
正反各掃一遍
一開始沒想到最高的可能會一樣高
加個maxH記起來 還能剪枝
class Solution {
public:
int trap(vector<int>& height) {
int maxH = 0;
int currH = 0;
int saved = 0, saving = 0;
for(int h: height){
if(currH <= h){
currH = h;
saved += saving;
saving = 0;
}
else{
saving += (currH - h);
}
}
if(saving == 0){
return saved;
}
maxH = currH;
currH = 0;
saving = 0;
for(int j = height.size()-1; j >= 0; j