2398.预算内的最多机器人数目

链接：2398.预算内的最多机器人数目
难度：Hard
标签：队列、数组、二分查找、前缀和、滑动窗口、堆（优先队列）
简介：请你返回在 不超过 budget 的前提下，你 最多 可以 连续 运行的机器人数目为多少。

题解 1 - python

• 编辑时间：2024-09-13
• 执行用时：1296ms
• 内存消耗：24.51MB
• 编程语言：python
• 解法介绍：由于连续，遍历所有可行区间，并记录当前区间内的最大值

from sortedcontainers import SortedList
class Solution:
    def maximumRobots(self, chargeTimes: List[int], runningCosts: List[int], budget: int) -> int:
        n = len(chargeTimes)
        l = 0
        nsum = 0
        sl = SortedList(key = lambda i: chargeTimes[i])
        get_budget = lambda l, r, sl, nsum: chargeTimes[sl[-1]] + len(sl) * nsum if l <= r else inf
        res = 0
        for r in range(n):
            sl.add(r)
            nsum += runningCosts[r]
            while l <= r and get_budget(l, r, sl, nsum) > budget:
                nsum -= runningCosts[l]
                sl.remove(l)
                l += 1
            if get_budget(l, r, sl, nsum) <= budget:
                res = max(res, len(sl))
        return res

题解 2 - python

• 编辑时间：2024-09-13
• 执行用时：372ms
• 内存消耗：24.41MB
• 编程语言：python
• 解法介绍：由于连续，遍历所有可行区间，并记录当前区间内的最大值，利用单调队列快速获取区间最大值。

from sortedcontainers import SortedList
class Solution:
    def maximumRobots(self, chargeTimes: List[int], runningCosts: List[int], budget: int) -> int:
        n = len(chargeTimes)
        l = 0
        nsum = 0
        q = deque()
        get_budget = lambda l, r, nmax, nsum: nmax + (r - l + 1) * nsum if l <= r else inf
        res = 0
        for r in range(n):
            while q and chargeTimes[q[-1]] < chargeTimes[r]: q.pop()
            q.append(r)
            nsum += runningCosts[r]
            while l <= r and get_budget(l, r, chargeTimes[q[0]], nsum) > budget:
                nsum -= runningCosts[l]
                if q[0] == l: q.popleft()
                l += 1
            if q and get_budget(l, r, chargeTimes[q[0]], nsum) <= budget:
                res = max(res, r - l + 1)
        return res