力扣刷题——2398. 预算内的最多机器人数目

由题目中求“最多可以连续运行的机器人数目”可知，求的是数组子数组的长度，那么就可以直接使用滑动窗口求解。配合前缀和，可以快速的求得滑动窗口内的运行时间和。那么编写代码如下：

int maximumRobots(vector<int> &chargeTimes, vector<int> &runningCosts, long long budget)
{
    int n = chargeTimes.size();
    vector<long long> subSum;

    subSum.emplace_back(0);
    for (int i = 0; i < n; i++)
    {
        subSum.emplace_back(subSum[i] + runningCosts[i]);
    }

    long long curCost = 0;
    int left = 0;
    int maxCharge;
    int res = 0;
    for (int right = 0; right < n; right++)
    {
        curCost = subSum[right + 1] - subSum[left];
        maxCharge = chargeTimes[left];
        for (int i = left + 1; i <= right; i++)
            maxCharge = max(maxCharge, chargeTimes[i]);
        int temRes = right - left + 1;
        curCost = curCost * temRes + maxCharge;
        if (curCost <= budget)
        {
            res = max(res, temRes);
        }
        else
        {
            left++;
        }
    }
    return res;
}

但是这样会超时，这是因为这段代码，对滑动窗口内的最大充电时间的维护是一个暴力算法，会导致算法整体的时间复杂度到O(n^2)。可以考虑用一个有序的数组来维护滑动窗口内的最大充电时间。比如红黑树，结构中最后一个元素为最大充电时间，在窗口增大缩小时，也能够很快的进行元素的删除和增加，那么有以下实现：

int maximumRobots(vector<int> &chargeTimes, vector<int> &runningCosts, long long budget)
{
    int n = chargeTimes.size();
    vector<long long> subSum;
    map<int, int> mp;
    subSum.emplace_back(0);
    for (int i = 0; i < n; i++)
    {
        subSum.emplace_back(subSum[i] + runningCosts[i]);
    }

    long long curCost = 0;
    int left = 0;
    int res = 0;
    for (int right = 0; right < n; right++)
    {
        curCost = subSum[right + 1] - subSum[left];
        mp[chargeTimes[right]]++;
        int temRes = right - left + 1;
        curCost = curCost * temRes + (--mp.end())->first;
        if (curCost <= budget)
        {
            res = max(res, temRes);
        }
        else
        {
            if (--mp[chargeTimes[left]] == 0)
                mp.erase(chargeTimes[left]);
            left++;
        }
    }
    return res;
}

用红黑树的方法很好理解，但是有点杀鸡用牛刀的意思。。。实现还有优化空间，可以考虑用一个双端队列实现单调队列，以此维护窗口内的最大充电时间，队列的首个元素为最大充电时间。在窗口右拓的时候，可以从后往前舍弃队列中的元素；而在窗口左缩的时候，可以从前往后弹出元素。在队列中存入最大充电时间的下标，将更加容易实现这个代码：

int maximumRobots(vector<int> &chargeTimes, vector<int> &runningCosts, long long budget)
{
    int n = chargeTimes.size();
    vector<long long> subSum;
    deque<int> dq;
    subSum.emplace_back(0);
    for (int i = 0; i < n; i++)
    {
        subSum.emplace_back(subSum[i] + runningCosts[i]);
    }

    long long curCost = 0;
    int left = 0;
    int res = 0;
    for (int right = 0; right < n; right++)
    {
        while (!dq.empty() && chargeTimes[dq.back()] <= chargeTimes[right])
            dq.pop_back();
        dq.push_back(right);

        while (!dq.empty() && (subSum[right + 1] - subSum[left]) * (right - left + 1) + chargeTimes[dq.front()] > budget)
        {
            if (dq.front() == left)
                dq.pop_front();
            left++;
        }

        if (!dq.empty())
            res = max(res, right - left + 1);
    }
    return res;
}