温州优化网站,长沙企业网站seo,企业网页设计教程,软件商城免费下载app我第一个手搓的hard的单调队列题目......灵神yyds
思路解析: 我做的时候感觉这个题目有点歧义,我以为他的连续运行是时间上连续,所以我开始写的代码是选择最多的子序列(可以不连续),使得不超过budget,这个求最多子序列的代码会在最后给出,不保证完全正确(因为没有太多测试点),…
我第一个手搓的hard的单调队列题目......灵神yyds
思路解析: 我做的时候感觉这个题目有点歧义,我以为他的连续运行是时间上连续,所以我开始写的代码是选择最多的子序列(可以不连续),使得不超过budget,这个求最多子序列的代码会在最后给出,不保证完全正确(因为没有太多测试点),但是逻辑上是没问题的,可以作为思路看看. 下面说说这个 要求连续的子序列 的个数最大值怎么求解 首先数据量5*1e4最多是O(nlogn) 注意到每次right(子序列的右边界)加一之后,左边界都可能不变或者回缩,所以我们可以使用滑动窗口的思想,那么因为max(chargeTimes)比较难求,耗时较长,所以我们可以使用单调队列来维护最大值,来实现O(1)时间内取出当前最大chargeTimes, (by the way, 我们也可以使用稀疏表来实现O(1),但是建表的过程是O(nlogn)的,不如单调队列,感兴趣的童鞋可以试试), 而对于sum(runningCosts),我们只需要一个sums记录一下即可,至于数目,我们可以使用一个cur表示当前的数量,使用ansmax(ans,cur)更新即可. 下面具体说一说单调队列的维护: 首先我们需要让单调队列来维护当前的最大值,也就是遇到比队尾小的直接加入,遇到比队尾大的,把队尾弹出再加入. 至于相等的元素可以直接加入,也可以把和它相等的元素都弹出去之后,再加入.这是因为我们不关注最大值的个数,只关注最大值,就算当前队列里面最大值的个数不对,但是他依然能够成功维护当前窗口最大值,这是因为我们当前的窗口是 [left, i],只有left等于dq.front()才会pop_front(). 之后我们判断当前区间的[left, i]是否再预算里面, yes- 更新ans, no-说明左边界要右移,但是我们每轮循环至多只用移动一位(因为 i 每次也只是加一),再更新sum,如果left等于dq.front(),那么说明当前front不能用了,pop_front. by the way,这也是单调队列的第二种模板,也即使用left和i表示当前区间,利用滑动窗口的特点,每次左边界不变或者收缩,不变的时候更新ans,收缩的时候判断当前队头还能不能使用
代码如下
class Solution {
public: int maximumRobots(vectorint chargeTimes, vectorint runningCosts, long long budget) {int lenchargeTimes.size();dequeint dq;int ans0,left0; long long sum0;for(int i0;ilen;i){while(dq.size() chargeTimes[i]chargeTimes[dq.back()]){dq.pop_back();}dq.push_back(i);sumrunningCosts[i];if(chargeTimes[dq.front()](i-left1)*sum budget){ansmax(ans,i-left1);}else{ sum-runningCosts[left];if(leftdq.front()) dq.pop_front();left;}}return ans;}
}; 那么如果我们要求的是 不连续的最长子序列呢, 那么首先我们需要按照runningcosts来做一个升序排序,这样我们如果想要得到更长的子序列,就需要pop出去当前chargeTimes最大的元素,这样才有可能得到一个更长的序列,代码如下: 而且注意这个时候在单调队列中,新元素如果和队尾相等,那么就应该加入进去,而不能pop_back()掉相等的元素了,因为这个时候用的就不是[left, i]的模板了,就没有if(leftdq.front())来保障最大值的安全了,每次不满足条件我们都是pop_front(),所以最大值的个数同样重要
class Solution {
public:
//我现在的这个做法是求的是不连续的最大int maximumRobots(vectorint chargeTimes, vectorint runningCosts, long long budget) {int lenchargeTimes.size();vectorint index;for(int i0;ilen;i) index.push_back(i);sort(index.begin(),index.end(),[](const int a,const int b){if(runningCosts[a]!runningCosts[b]) return runningCosts[a]runningCosts[b];else return chargeTimes[a]chargeTimes[b];});dequeint dq;int ans0,cur0; long long sum0;for(int i0;ilen;i){int idxindex[i];while(dq.size() chargeTimes[idx]chargeTimes[dq.back()]){dq.pop_back();}dq.push_back(idx);sumrunningCosts[idx];if(chargeTimes[dq.front()](cur1)*sum budget){cur;ansmax(ans,cur);}else{//sum-runningCosts[dq.front()];dq.pop_front();cur--;}}return ans;}
};
