Re: [閒聊] 每日leetcode
繼續慢慢推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--){
if(currH == maxH) break;
if(currH <= height[j] ){
currH = height[j];
saved += saving;
saving = 0;
}
else{
saving += (currH - height[j]);
}
}
return saved;
}
};
--
心。郊遊
何必是遠方
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 39.10.50.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1716322200.A.062.html
討論串 (同標題文章)