以下是 LeetCode 2398 的 JavaScript 实现,使用滑动窗口 + 单调队列:

```javascript
/**
 * @param {number[]} chargeTimes
 * @param {number[]} runningCosts
 * @param {number} budget
 * @return {number}
 */
var maximumRobots = function(chargeTimes, runningCosts, budget) {
    const n = chargeTimes.length;
    const deque = []; // 单调递减队列,存储索引,队首为当前窗口最大值
    let sumRunning = 0;
    let left = 0;
    let ans = 0;

    for (let right = 0; right < n; right++) {
        // 1. 维护单调递减队列,保证队首是窗口内 chargeTimes 的最大值
        while (deque.length > 0 && chargeTimes[deque[deque.length - 1]] <= chargeTimes[right]) {
            deque.pop();
        }
        deque.push(right);

        // 2. 扩大窗口,累加 runningCosts
        sumRunning += runningCosts[right];

        // 3. 计算当前窗口的总费用并检查是否超预算
        const len = right - left + 1;
        let maxCharge = chargeTimes[deque[0]];
        let cost = maxCharge + len * sumRunning;

        // 4. 若费用超出预算,缩小窗口
        while (cost > budget && left <= right) {
            // 如果左边界恰好是当前最大值,从队列中移除
            if (deque[0] === left) {
                deque.shift();
            }
            sumRunning -= runningCosts[left];
            left++;
            
            if (left <= right) {
                const newLen = right - left + 1;
                maxCharge = deque.length > 0 ? chargeTimes[deque[0]] : 0;
                cost = maxCharge + newLen * sumRunning;
            } else {
                cost = 0; // 窗口为空,费用为0
            }
        }

        // 5. 更新最大长度
        ans = Math.max(ans, right - left + 1);
    }
    
    return ans;
};
```

更简洁的版本

```javascript
var maximumRobots = function(chargeTimes, runningCosts, budget) {
    const n = chargeTimes.length;
    const deque = [];
    let sumRunning = 0;
    let left = 0;
    let ans = 0;

    for (let right = 0; right < n; right++) {
        // 维护单调递减队列
        while (deque.length && chargeTimes[deque[deque.length - 1]] <= chargeTimes[right]) {
            deque.pop();
        }
        deque.push(right);
        
        sumRunning += runningCosts[right];
        
        // 超预算时收缩窗口
        while (deque.length && chargeTimes[deque[0]] + (right - left + 1) * sumRunning > budget) {
            if (deque[0] === left) deque.shift();
            sumRunning -= runningCosts[left];
            left++;
        }
        
        ans = Math.max(ans, right - left + 1);
    }
    
    return ans;
};
```

算法说明

核心思路:

1. 滑动窗口:维护一个符合条件的连续子数组 [left, right]
2. 单调队列:维护窗口内 chargeTimes 的最大值,队首始终是最大值索引
3. 费用计算:maxCharge + 窗口长度 × 窗口内 runningCosts 和

时间复杂度: O(n)
空间复杂度: O(n)

关键点:

· 使用数组模拟双端队列(push/pop 操作队尾,shift 操作队首)
· 当费用超过 budget 时,右移 left 指针缩小窗口
· 每次移动 left 时,如果它恰好是最大值索引,需要从队列中移除

 

Logo

中国智能体开发者社区,聚焦智能体与大模型开发,提供前沿资讯、实用工具链、开源项目及行业案例。通过技术沙龙、开发者大赛等活动,促进经验交流与协作,助力开发者快速构建创新智能应用。

更多推荐