预算内的最多机器人数目

The solution uses a sliding window approach combined with a deque to maintain the maximum charge time within the current window. As we iterate through the robots using a right pointer, we add the current robot's charge time to the deque in a way that ensures the deque is always sorted in descending order. This allows the largest element (maximum charge time) to always be at the front of the deque. We also keep a running sum of the running costs. At each step, we check if the sum of the maximum charge time and the product of the number of robots and the sum of running costs fits within the budget. If it does, we update our answer. If it doesn't, we adjust the window by moving the left pointer to the right, ensuring the properties of the deque and updating the running costs sum accordingly.

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def maximumRobots(self, chargeTimes: List[int], runningCosts: List[int], budget: int) -> int:
        n = len(chargeTimes)
        left = 0
        dq, costs = deque(), 0
        ans = 0
        for right in range(n):
            # Maintain a decreasing deque of charge times
            while dq and chargeTimes[right] > dq[-1]:
                dq.pop()
            dq.append(chargeTimes[right])
            # Update the total running costs for the current window
            costs += runningCosts[right]
            # Check if the current window fits the budget
            if dq[0] + (right - left + 1) * costs <= budget:
                ans = max(ans, right - left + 1)
            else:
                # Adjust the window from the left if budget is exceeded
                if dq[0] == chargeTimes[left]:
                    dq.popleft()
                costs -= runningCosts[left]
                left += 1
        return ans