推 wwndbk: 大師 04/12 11:03
推 oinishere: 大師 04/12 11:11
→ SecondRun: 大師 04/12 12:11
42. Trapping Rain Water
思路
當格能裝的水 = min(當格以左的最高高度,當格以右的最高高度) - 當格高度
然後要記得卡0 裝的水不會是負的
左半邊maximum就單純跟著for loop更新
右半邊maximum我先init一個right_maximum vector:
right_maximum[i] = max(height[i+1:])
然後就單純for loop結束
int trap(vector<int>& height) {
int left_maximum=0;
vector<int> right_maximum(height.size(), 0);
int sum=0;
// init right_maximum
int right_max_cur=0;
for(int i=height.size()-2; i>=0; i--)
{
right_max_cur = max(right_max_cur, height[i+1]);
right_maximum[i] = right_max_cur;
}
for(int i=0; i<height.size(); i++)
{
// add water at idx i
sum += max((min(left_maximum, right_maximum[i]) - height[i]), 0);
// update left maximum
left_maximum = max(left_maximum, height[i]);
}
return sum;
}
我好像幾個月沒寫hard了==
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.138.89.231 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1712890984.A.D30.html