Re: [閒聊] 每日leetcode
看板Marginalman作者DJYOSHITAKA (franchouchouISBEST)時間1年前 (2024/04/12 11:03)推噓2(2推 0噓 1→)留言3則, 3人參與討論串112/1548 (看更多)
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
推
04/12 11:03,
1年前
, 1F
04/12 11:03, 1F
推
04/12 11:11,
1年前
, 2F
04/12 11:11, 2F
→
04/12 12:11,
1年前
, 3F
04/12 12:11, 3F
討論串 (同標題文章)
完整討論串 (本文為第 112 之 1548 篇)：