Re: [閒聊] 每日leetcode
2106. Maximum Fruits Harvested After at Most K Steps
思路:
這題為sliding windows
假設要取得fruits[start]到fruits[end]這兩點間的水果
有分兩種走法
先往左再往右花費步數為 : fruits[end][0] + startPos - 2*fruits[start][0]
先往右再往走花費步數為 : 2*fruits[end][0] - startPos - fruits[start][0]
就先找出fruits中位置在[startPos-k, startPos+k]範圍內的點
接著從最左邊的點開始走
並且判斷上面兩種走法中的最小步數是否大於k
是的話就移動start，一直到小於k為止
就這樣一直紀錄最大獲得的水果數量
就能得到答案了
c++ code :
class Solution {
public:
int maxTotalFruits(vector<vector<int>> &fruits, int startPos, int k)
{
int start = 0, n = fruits.size(), sum = 0, ans = 0;
while (start < n && fruits[start][0] < startPos - k) {
start++;
}
for (int end = start; end < n && fruits[end][0] <= startPos + k; end++
) {
sum += fruits[end][1];
while (min(fruits[end][0] - 2 * fruits[start][0] + startPos,
2 * fruits[end][0] - fruits[start][0] - startPos) > k)
{
sum -= fruits[start][1];
start++;
}
ans = max(ans, sum);
}
return ans;
}
};
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.71.215.96 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1754194043.A.DF5.html
推
08/03 12:08,
4月前
, 1F
08/03 12:08, 1F
→
08/03 14:12,
4月前
, 2F
08/03 14:12, 2F
討論串 (同標題文章)
完整討論串 (本文為第 1490 之 1548 篇)：