作者推荐
【动态规划】【广度优先】LeetCode2258:逃离火灾
本文涉及的基础知识点
二分查找算法合集
滑动窗口
单调队列:计算最大值时,如果前面的数小,则必定被淘汰,前面的数早出队。
题目
你有 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 * 104
1 <= chargeTimes[i], runningCosts[i] <= 105
1 <= budget <= 1015
双指针
分析
本质是子数组,我们可以枚举起点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
相关下载
想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
我想对大家说的话 |
---|
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。 |
子墨子言之:事无终始,无务多业 |
。也就是我们常说的专业的人做专业的事。 |
|如果程序是一条龙,那算法就是他的是睛|
测试环境
操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境:
VS2022 C++17