二分查找|雙指針:LeetCode:2398.預算內的最多機器人數目

作者推薦

本文涉及的基礎知識點

二分查找算法合集
滑動窗口
單調隊列：計算最大值時，如果前面的數小，則必定被淘汰，前面的數早出隊。

題目

你有 n 個機器人，給你兩個下標從 0 開始的整數數組 chargeTimes 和 runningCosts ，兩者長度都為 n 。第 i 個機器人充電時間為 chargeTimes[i] 單位時間，花費 runningCosts[i] 單位時間運行。再給你一個整數 budget 。
運行 k 個機器人總開銷是 max(chargeTimes) + k * sum(runningCosts) ，其中 max(chargeTimes) 是這 k 個機器人中最大充電時間，sum(runningCosts) 是這 k 個機器人的運行時間之和。
請你返回在不超過 budget 的前提下，你最多可以連續運行的機器人數目為多少。
示例 1：
輸入：chargeTimes = [3,6,1,3,4], runningCosts = [2,1,3,4,5], budget = 25
輸出：3
解釋：
可以在 budget 以內運行所有單個機器人或者連續運行 2 個機器人。
選擇前 3 個機器人，可以得到答案最大值 3 。總開銷是 max(3,6,1) + 3 * sum(2,1,3) = 6 + 3 * 6 = 24 ，小于 25 。
可以看出無法在 budget 以內連續運行超過 3 個機器人，所以我們返回 3 。
示例 2：
輸入：chargeTimes = [11,12,19], runningCosts = [10,8,7], budget = 19
輸出：0
解釋：即使運行任何一個單個機器人，還是會超出 budget，所以我們返回 0 。
參數范圍：
chargeTimes.length == runningCosts.length == n
1 <= n <= 5 * 10⁴
1 <= chargeTimes[i], runningCosts[i] <= 10⁵
1 <= budget <= 10¹⁵

雙指針

分析

本質是子數組，我們可以枚舉起點left ，子數組[left,righ)是不超預算的最長子數組。

時間復雜度

O(n)，枚舉left和right都是O(n)，right沒有從新開始，所有總時間復雜度是O(n)。

代碼

核心代碼

class Solution {
public:
int maximumRobots(vector& chargeTimes, vector& runningCosts, long long budget) {
m_c = chargeTimes.size();
int iRet = 0;
long long llSum = 0;
std::deque vMaxIndex;
for (int left = 0, right = 0; left < m_c; left++)
{
if (right < left)
{
llSum = 0;
right = left;
vMaxIndex.clear();
}
while (right < m_c)
{
while (vMaxIndex.size() && (chargeTimes[vMaxIndex.back()] <= chargeTimes[right]))
{
vMaxIndex.pop_back();
}
vMaxIndex.emplace_back(right);
const long long llNew = (llSum + runningCosts[right]) * (right-left+1) + chargeTimes[vMaxIndex.front()];
if (llNew > budget)
{
break;// [left,right)超出預算，有多個right，取最小的按個
}
llSum += runningCosts[right];
right++;
}
iRet = max(iRet, right - left);
llSum -= runningCosts[left];
if (vMaxIndex.front() == left)
{
vMaxIndex.pop_front();
}
}
return iRet;
}
int m_c;
};

測試用例

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{if (v1.size() != v2.size()){assert(false);return;}for (int i = 0; i < v1.size(); i++){assert(v1[i] == v2[i]);}
}template<class T>
void Assert(const T& t1, const T& t2)
{assert(t1 == t2);
}int main()
{vector<int> chargeTimes, runningCosts;long long budget;{Solution slu;chargeTimes = { 3,6,1,3,4 }, runningCosts = { 2,1,3,4,5 }, budget = 25;auto res = slu.maximumRobots(chargeTimes, runningCosts, budget);Assert(3, res);}{Solution slu;chargeTimes = { 11,12,19 }, runningCosts = { 10,8,7 }, budget = 19;auto res = slu.maximumRobots(chargeTimes, runningCosts, budget);Assert(res, 0);}{Solution slu;chargeTimes = { 19,63,21,8,5,46,56,45,54,30,92,63,31,71,87,94,67,8,19,89,79,25 }, runningCosts = { 91,92,39,89,62,81,33,99,28,99,86,19,5,6,19,94,65,86,17,10,8,42 }, budget = 85;auto res = slu.maximumRobots(chargeTimes, runningCosts, budget);Assert(res, 1);}//CConsole::Out(res);
}

優化

如果不存在以left開始的合法子數組，right和left相同，left++后，right就小于left ，需要特殊處理。
我們換成先枚舉right，再枚舉left。左閉右閉空間[left,right]是最長合法子數組。但不存在合法子數組時：left等于right+1，right++后，兩者就相等了，無需特殊處理。

代碼

class Solution {
public:int maximumRobots(vector<int>& chargeTimes, vector<int>& runningCosts, long long budget) {m_c = chargeTimes.size();int iRet = 0;long long llSum = 0;std::deque<int> vMaxIndex;for (int right = 0, left = 0; right < m_c; right++){	while (vMaxIndex.size() && (chargeTimes[vMaxIndex.back()] <= chargeTimes[right])){vMaxIndex.pop_back();				}vMaxIndex.emplace_back(right);llSum += runningCosts[right];while (left <= right ){		const long long llNew = llSum * (right-left+1) + chargeTimes[vMaxIndex.front()];if (llNew > budget){llSum -= runningCosts[left];if (vMaxIndex.front() == left){vMaxIndex.pop_front();}left++;}else{break;}}iRet = max(iRet, right - left+1);			}return iRet;}int m_c;
};

二分查找

尋找最后一個不超預算的連續機器人長度，左開右閉。時間復雜度😮(longnn)。二分長度，時間復雜度度O(logn);指定長度枚舉所有終點，時間復雜度O(n)。

代碼

class Solution {
public:
int maximumRobots(vector& chargeTimes, vector& runningCosts, long long budget) {
m_c = chargeTimes.size();
int left = 0, right = m_c + 1;
while (right - left > 1)
{
const auto mid = left + (right - left) / 2;
if (NeedBudget(chargeTimes, runningCosts, mid) <= budget)
{
left = mid;
}
else
{
right = mid;
}
}
return left;
}
long long NeedBudget(vector& chargeTimes, vector& runningCosts, int len)
{
long long llSum = 0;
std::deque vMaxIndex;
int i = 0;
for (; i < len; i++)
{
llSum += runningCosts[i];
while (vMaxIndex.size() && (chargeTimes[vMaxIndex.back()] <= chargeTimes[i]))
{
vMaxIndex.pop_back();
}
vMaxIndex.emplace_back(i);
}
long long llNeed = llSum * len + chargeTimes[vMaxIndex.front()];
for (; i < m_c; i++)
{
llSum += runningCosts[i]- runningCosts[i-len];
while (vMaxIndex.size() && (chargeTimes[vMaxIndex.back()] <= chargeTimes[i]))
{
vMaxIndex.pop_back();
}
vMaxIndex.emplace_back(i);
if (vMaxIndex.front() == i-len)
{
vMaxIndex.pop_front();
}
llNeed = min(llNeed,llSum * len + chargeTimes[vMaxIndex.front()]);
}
return llNeed;
}
int m_c;
};

擴展閱讀

視頻課程

有效學習：明確的目標及時的反饋拉伸區（難度合適），可以先學簡單的課程，請移步CSDN學院，聽白銀講師（也就是鄙人）的講解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成戰斗了，為老板分憂，請學習C#入職培訓、C++入職培訓等課程
https://edu.csdn.net/lecturer/6176

我想對大家說的話
聞缺陷則喜是一個美好的愿望，早發現問題，早修改問題，給老板節約錢。
子墨子言之：事無終始，無務多業

測試環境

操作系統：win7 開發環境： VS2019 C++17
或者操作系統：win10 開發環境：

VS2022 C++17

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/210850.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/210850.shtml
英文地址，請注明出處：http://en.pswp.cn/news/210850.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！