2398. Max Robots

Maximum Number of Robots Within Budget

通过率38%徘徊 的第2398号难题 事实上只是想知道答题人懂不懂得一个基本意识：审题

一旦有好好审题 才会确信 单调队列、滑动窗口、前缀和 三宝能合而为一拿下

永远只带著自然数的chargeTimes和runningCosts

输入有两项阵列：chargeTimes和runningCosts 双方长度皆为n

第$i$索引上分别是第$i$台机器人充电时间和运行成本

每一个机器人的充电时间和运行成本都是 自然数 本来嘛 成本若是负数

岂不是材料商把原物料『倒贴』给工厂？这样做出来的机器人还靠谱？😏

同理 充电时间要是有负数 那世界崩塌了是吧？

输入的第三项 是另一个正整数budget代表预算 而选中数量为k的机器人来运行有公式：

总开销 = $k$个机器人中最大的充电时间 + $k$ * 全部k个机器人们运行成本总和

因此题目问的是 在总开销不超过预算的前提下 最多能 连续 抓多少台机器人同时运行

注意有 连续 这个形容词 它不接受同时抓第$i$台和第$i + 2$台 但不抓第$i + 1$台的跳跳虎模式

看到这儿 我们就会察觉一个巧妙的事实：若$0 \leq i \leq j \leq l < n$

一旦连抓第$i$到第$j$台机器人时 发现这$j + 1 - i$台机器人的总开销超过预算

那我们抓第$i$到第$l$台机器人时 一样会看见这$l + 1 - i$台机器人总开销超过预算 甚至更严重

为什么呢？ 第$i$到$j$台机器人中最大的充电时间 $\leq$ 第$i$到$l$台机器人中最大的充电时间 前者是后者的子集

公式中的『$k$个机器人中最大的充电时间』没法下降

又刚才说过运行成本都是自然数 因此第$i$到$l$台机器人运行成本总和 > 第$i$到$j$台机器人运行成本总和

$k$随著机器人越抓越多只会上涨 既然三个子项都不可能下降 那总开销就不可能下降了

于是有个结论：一旦遍历时第$i$到$j$台机器人总开销超预算 非得放弃第$i$台机器人 才有机会压回预算内

如此而言 是不是就有 单调性 可言呢？ 失效的不会复活 继续往下遍历即可 无需回头再扫描

听著就是时间复杂度O(n)解有望 不过肯定还是要用恰当的数据结构 才能让单调性确实兑现成O(n)

数据结构三宝

1. 滑动窗口：定好搜查范围

看到这我们确定了 遍历所有机器人的充电时间和运行成本时 需要开两个指针：startIdx和endIdx

反映的是当前抓了第startIdx到endIdx台 总计endIdx + 1 - startIdx这么多机器人在测算

一旦总开销超标 就必须递增startIdx 直到总开销回到预算内 或者startIdx > endIdx为止

2. 单调队列：窗口内的最大充电时间

递增endIdx时 需要知道第startIdx到第endIdx这帮机器人中最大的充电时间是多少

那我们可用 单调递减队列 来追踪最大值 先让第endIdx台机器人的充电时间和队列尾比较

只要队列尾的充电时间 $\leq$ 第endIdx台机器人的充电时间 队列尾自然失去作用 弹走就对啰

直到队列整个被弹光了 或者是第endIdx台机器人的充电时间 < 队列尾的充电时间 才停止比较

同时我们还得在startIdx上升时 检查队首的索引是否摔出窗外了 是的话就弹走队列之首

其馀队列内的成员自然往前一顺位 更新窗口内的最大充电时间

3. 前缀和：窗口内的运行成本总和

最后还差一个windowTotalCost变量 记录第startIdx到第endIdx台机器人运行成本的总和

递增endIdx时 把第endIdx台机器人的运行成本 加到windowTotalCost上

同理 递增startIdx时 把第startIdx台机器人的运行成本 从windowTotalCost上减掉

这样便能每次都拥有正确的窗口内运行成本总和 由此可见遍历endIdx过程中

一旦startIdx不再上升 那么窗口内的机器人自然不会产生超预算的总开销

这群机器人总数便是 endIdx + 1 - startIdx 如此多啰 (1)

在滑动窗口的设计时 我们有说是可能发生startIdx 不停递增 直到startIdx > endIdx

因此对于每个endIdx来说 startIdx最大是可能到endIdx + 1的 但这完全不用怕 因为

(1)中的机器人总数算式 会让此刻endIdx + 1 - startIdx = 0 也就是不抓任何机器人了 这是合法的情况

于是剩下的就是比较目前得出的机器人总数 有无胜过历史最大值 最后返回历史最大值即结案啰～～

真的就是好好看清题目的Constraints 联想到在如此限制下 哪些数据结构能最快地保证正确性 时空复杂度双双O(n)

C++

#include <vector>
#include <queue>
using namespace std;

int countMaxRobots(vector<int> &chargeTimes, vector<int> &runningCosts, long long budget) // LeetCode Q.2398.
{
    int maxRobotsCount = 0; // Base case.

    long long windowTotalCost = 0;

    int startIdx = 0;
    deque<pair<int, int>> queue; // Format: {charge time, idx}.

    for (int endIdx = 0; endIdx < chargeTimes.size(); endIdx++)
    {
        windowTotalCost += runningCosts[endIdx];

        while (!queue.empty() && queue.back().first <= chargeTimes[endIdx])
            queue.pop_back();

        queue.push_back({chargeTimes[endIdx], endIdx});

        int robotsCount = endIdx + 1 - startIdx;
        int maxChargeTime = queue.front().first;

        while (budget < maxChargeTime + robotsCount * windowTotalCost)
        {
            windowTotalCost -= runningCosts[startIdx];

            startIdx++;
            robotsCount--;

            if (!queue.empty() && queue.front().second < startIdx)
                queue.pop_front();

            if (startIdx > endIdx)
                break; // 0 robots at hand.
        }

        if (robotsCount > maxRobotsCount)
            maxRobotsCount = robotsCount;
    }

    return maxRobotsCount;
}

Python

from collections import deque


def count_max_robots(charge_times: list[int], running_costs: list[int], budget: int):  # LeetCode Q.2398.
    max_robots_count = 0  # Base case.

    window_total_cost = 0

    queue: deque[tuple[int, int]] = deque([])  # Format: (charge time, idx).

    start_idx = 0
    for end_idx, charge_time in enumerate(charge_times):
        window_total_cost += running_costs[end_idx]

        while queue and queue[-1][0] <= charge_time:
            queue.pop()

        queue.append((charge_time, end_idx))

        robots_count = end_idx + 1 - start_idx
        max_charge_time = queue[0][0]

        while budget < max_charge_time + robots_count * window_total_cost:
            window_total_cost -= running_costs[start_idx]

            robots_count -= 1
            start_idx += 1

            if queue and queue[0][1] < start_idx: queue.popleft()

            if start_idx > end_idx: break  # 0 robots at hand.

        if robots_count > max_robots_count: max_robots_count = robots_count

    return max_robots_count

延伸问题

回过头看 题目那句必须 连续取机器人 的叙述 各位还觉得是条罗嗦限制吗🤓