thetheOrange的笔记

发表于 更新于 分类于 本文字数： 3.8k 阅读时长 ≈ 7 分钟

题目描述

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

你有 n 个机器人，给你两个下标从 0 开始的整数数组 chargeTimes 和 runningCosts ，两者长度都为 n 。第 i 个机器人充电时间为 chargeTimes[i] 单位时间，花费 runningCosts[i] 单位时间运行。再给你一个整数 budget 。

运行 k 个机器人 总开销 是 max(chargeTimes) + k * sum(runningCosts) ，其中 max(chargeTimes) 是这 k 个机器人中最大充电时间，sum(runningCosts) 是这 k 个机器人的运行时间之和。

请你返回在 不超过 budget 的前提下，你 最多 可以 连续 运行的机器人数目为多少。

1
2
3
4
5
6
7
8
输入：chargeTimes = [3,6,1,3,4], runningCosts = [2,1,3,4,5], budget = 25

输出：3

解释：
可以在 budget 以内运行所有单个机器人或者连续运行 2 个机器人。
选择前 3 个机器人，可以得到答案最大值 3 。总开销是 max(3,6,1) + 3 * sum(2,1,3) = 6 + 3 * 6 = 24 ，小于 25 。
可以看出无法在 budget 以内连续运行超过 3 个机器人，所以我们返回 3 。

解题思路

这题的关键是连续。

因为连续，我们可以得出这样一个结论：

假设说有k为最多的可以连续运行机器人数目，那么必定有 k-1，k-2，k-3 ... 的机器人满足条件。

反过来，那就必定有 k+1，k+2，k+3 ... 的机器人不满足条件。

而且k的范围必定在 [0, chargeTimes.size()] 里

这样想，其实我们可以使用二分查找，来查找我们的答案。因为对于k的范围而言，k的范围可以视为一个单调递增的数组。而k相当于二分查找中的mid，mid左边的数满足条件，mid右边的数不满足条件。

为了方便，我们使用开区间写法（不用考虑mid+1）

1
2
3
4
5
6
7
int left = 0, right = chargeTimes.size()+1;
while (left + 1 < right) {
    int mid = (left + right) / 2;
    if (check(mid)) left = mid; 
    else right = mid;
} 
return left;

这个时候 left 就是答案。

这里的check函数的作用是，检测k个连续的机器人是否合法，合法的标准是 max(chargeTimes) + k * sum(runningCosts)。转换一下，其实可以翻译成，在一个数组中，取n个长度为k的滑动窗口，判断这n个窗口中，是否存在一个窗口满足条件。

这样看，是不是和239. 滑动窗口最大值 的思路十分相似。

接下来，我们先来解决这个题目。

前置题目和单调队列

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

对于这道题而言，暴力解法就是取长度为k的滑动窗口，遍历整个数组，依次取窗口的最大值，最后返回结果即可。假设每个窗口大小为1的情况下，暴力解法的时间复杂度为O(n^2)，会明显地超时。

另一种想法是，每次的滑动窗口的最大值，并不需要我们每次重新求值，而是可能和上次的值有关。

例如，[1,3,-1,-3,5,3,6,7]

1
2
3
4
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3

第一个窗口和第二个窗口的最大值其实是重复的，因为第二个滑动窗口向右滑动的时候，新加入的-3并没有大过3，而且，左边的边界收缩的时候，3也并没有移除，所以取3。

既然如此，我们只要维护每个窗口的最大值就行了？

最直白的想法，可能是使用优先队列priority_queue， 但是对于优先队列，找到最大值很容易，移除元素很困难，因为我们要维护最大值。

如果有一种队列能够保持最大值且删除元素很容易，那就好了

抱着这样的想法，我们可以引入单调队列。

push时，每次都保证队头元素为最大的元素。

1
2
3
4
5
6

void push(int val) {
    while (!q.empty() && q.back() < val) q.pop_back();
    q.push_back(val);
}

pop时，当队头元素为目标元素时，应该将其移除。

1
2
3
4
5

void pop(int val) {
    if (!q.empty() && q.front() == val) q.pop_front();
}

这样，我们再使用滑动窗口的思想，当窗口长度为k时，取队头元素，使用pop(val)移除元素，不为k时，则维护最大值，使用push(val)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
public:
    deque<int> que;
    void pop(int val) {
        if (!this->que.empty() && this->que.front() == val) this->que.pop_front();
    }
    void push(int val) {
        while (!this->que.empty() && this->que.back() < val) this->que.pop_back(); // 比最大值小的数且在最大值前面的数无意义 可以直接去掉
        this->que.push_back(val);
    }
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int left = 0;
        vector<int> ret;
        for (int right = 0; right < nums.size(); ++right) {
            int len = right - left + 1;
            this->push(nums[right]);
            if (left <= nums.size() - k && len == k) {
                ret.push_back(this->que.front());
                this->pop(nums[left++]);
            }
        }
        return ret;
    }
};

解决本题

对于本题的max(chargeTimes) + k * sum(runningCosts)合法条件，max(chargeTimes)其实就是维护每个长度为k的滑动窗口的最大值，对于sum(runningCosts)，维护的是每一个窗口的总和。

这样一来，思路就很明显了。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

class Solution {
public:
    deque<int> q;
    void push(int val) {
        while (!q.empty() && q.back() < val) q.pop_back();
        q.push_back(val);
    }
    void pop(int val) {
        if (!q.empty() && q.front() == val) q.pop_front();
    }
    int maximumRobots(vector<int>& chargeTimes, vector<int>& runningCosts, long long budget) {
        function<bool(int)>check = [&](int k) {
            q.clear(); // 每次判断前 一定要进行初始化 否则会导致上一次的最大值残留
            // 求取每个窗口的最大值
            int l = 0, n = chargeTimes.size();
            long long sum = 0;
            for (int r = 0; r < n; ++r) {
                int len = r - l + 1;
                this->push(chargeTimes[r]);
                sum += runningCosts[r];
                if (l <= n - k && len == k) {
                    if ((q.front()+k*sum)<= budget) return true;
                    this->pop(chargeTimes[l]);
                    sum -= runningCosts[l++];
                }
            }
            return false;
        };
        int left = 0, right = chargeTimes.size()+1;
        while (left + 1 < right) {
            int mid = (left + right) / 2;
            if (check(mid)) left = mid;
            else right = mid;
        } 
        return left;
    }
};

时间、空间复杂度分析

以下n为chargeTimes数组的长度

时间：O((log 2)*n) 二分答案加滑动窗口
空间复杂度： O(n) 假如k为n时，需要申请大小为n的双端队列。

发表于 更新于 分类于 本文字数： 2.1k 阅读时长 ≈ 4 分钟

二分查找的流程

先来看一个问题：

力扣704 二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

这题的暴力解很容易想到，就是依次遍历，直到找到target，否则则返回-1。这样做的时间复杂度为O(n)

暴力解忽略了题目中有序数组的条件。在这种条件下，使用二分查找能节省大量的时间。

输入 nums = [5,7,7,8,8,10], target = 8

我们使用两个指针：左指针和右指针分别指向数组的0下标和len(nums)-1 (这里采用的是闭区间写法)

每次的循环中，我们取left和right区间中间的数(这里记为nums[mid])，将nums[mid]同target进行比较。

这时候有三种情况：

  1. nums[mid] > target 此时right应该缩小 即right = mid - 1
  2. nums[mid] < target 此时left应该前进 即left = mid + 1
  3. nums[mid] = target 此时返回mid即可

由此，我们就可以得到下面这段代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size()-1;
        while (l <= r) {
            int mid = l + (r - l) / 2; // 这里为了防止溢出
            if (target > nums[mid]) l = mid + 1;
            else if (target < nums[mid]) r = mid - 1;
            else return mid;
        }
        return -1; // 没有找到结果直接返回-1就好
    }
};

二分查找时间复杂度和空间复杂度

由于我们每次都是在中间选取，所以二分查找的时间复杂度应该为O(log 2)

二分查找算法中，因为只用了几个变量作为参数，所以空间复杂度为O(1)

二分查找的要求

是否能进行二分查找，要满足两个条件：

  1. 数组为顺序存储 (链表不适用)
  2. 数组中元素有序

数组为顺序存储这个条件比较好理解。如果题目给定的是一个链表的话，因为链表不能够直接从下标获取到元素，而是要通过遍历得到，所以对链表使用二分查找显然不是十分有效率。

数组中元素有序，这个条件的重点在有序。这里的有序当然不仅仅包含，单调递增或是单调递减，这里的有序可以理解为广义上的有序。例如力扣852. 山脉数组的峰顶索引，就不是按照所有元素单调性的有序进行存储，但是只要我们可以根据nums[mid]来确定数组元素的大小，就可以认定为有序。

四种情况的讨论

在二分查找中，抓住循环不变量很关键：

以704为例

[0, l-1] x < target
[r+1, n-1] x > target

在二分查找中，其实有四种情况：

  1. >=
  2. >
  3. <=
  4. <

我们来看这道题目 力扣34. 在排序数组中查找元素的第一个和最后一个位置

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

这道题目其实相当于让我们求第1和3种情况

我们先来求第三种情况 <=

1
2
3
4
5
6
7
8
9
int lower_bound(vector<int>& nums, int target) {
    int l = 0, r = nums.size()-1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (target > nums[mid]) l = mid + 1;
        else r = mid - 1;
    }
    return l;
}

事实上，<= 是能和其他三种情况相互转换的。

< target 可转化为 <= (target) - 1
> target 可转化为 >= (target + 1)
>= target 可转化为 (<= target + 1) - 1

那么，本题就可以先计算出<=的情况 再由此推出>=的情况

1
2
3
4
5
6
7
8
9
10
11
12
vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> res{-1, -1};
        int start = this->lower_bound(nums, target);
        // 如果没找到target
        if (start == nums.size() || nums[start] != target) {
            return res;
        }
        // >= target 可转化为 (<= target + 1) - 1
        int end = this->lower_bound(nums, target+1) - 1;
        res[0] = start; res[1] = end;
        return res;
    }

特别感谢

感谢灵神，给我带来的启发qwq

发表于 本文字数： 210 阅读时长 ≈ 1 分钟

基本格式

type + 描述

type类型

  • feat 新功能
  • fix/to
    • fix 产生diff并自动修复问题。适合一次提交直接修复格式
    • to 只产生diff不自动修复此问题。适合于多次提交。最终修复问题提交时使用fix
  • docs 提交文档
  • style 格式 不影响代码运行的变动
  • refactor 重构
  • perf 优化
  • test 测试 单元测试
  • chore 构建过程或辅助工具的变动
  • revert 回滚到上一个版本
  • merge 代码合并
  • sync 同步主线或分支的bug
0%