前言
这周忙废了…挑战一天写完一周的题。
本周主题:双指针、枚举、单调队列
题目:
- 240910每日一题—Count Increasing Quadruplets
- 240912每日一题—Find the Maximum Number of Marked Indices
- 240913每日一题—Maximum Number of Robots Within Budget
Maximum Number of Robots Within Budget
Maximum Number of Robots Within Budget
You have n robots. You are given two 0-indexed integer arrays, chargeTimes and runningCosts, both of length n. The ith robot costs chargeTimes[i] units to charge and costs runningCosts[i] units to run. You are also given an integer budget.
The total cost of running k chosen robots is equal to max(chargeTimes) + k * sum(runningCosts), where max(chargeTimes) is the largest charge cost among the k robots and sum(runningCosts) is the sum of running costs among the k robots.
Return the maximum number of consecutive robots you can run such that the total cost does not exceed budget.
首先注意题目要求启动的机器人序列连续,则构成一个窗口,窗口内计算cost要小于budget且窗口尽量大。每次窗口移动可能会影响两个点进而影响窗口cost,一个是最大充电时间,一个是总体启动时间消耗。则这道题可以看为Sliding Window Maximum的变体题目。
因此先来把Sliding Window Maximum的单调队列做法搞懂。
PS:这道题我之前也写了一个TreeMap的题解,比较复杂,正好这次学一下单调队列的解法。
「单调队列」即满足单调性的双端队列,双端队列左侧为队首,右侧为队尾。
前置题目:Sliding Window Maximum
Sliding Window Maximum
You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
Return the max sliding window.
题目比较容易理解,就是取一个定长的滑窗在数组上滑出若干个最值,难点就是用尽量少的时间计算每个窗口中的最值。
由于我们需要求出的是滑动窗口的最大值,如果当前的滑动窗口中有两个下标 $i$ 和 $j$, 其中 $i$ 在 $j$的左侧 $(i<j)$ ,并且 $i$ 对应的元素不大于 $j$ 对应的元素(nums $[i] \leq n u m s[j]$) ,则当滑动窗口向右移动时,只要 $i$ 还在窗口中,那么 $j$ 一定也还在窗口中,这是 $i$ 在 $j$ 的左侧所保证的。因此, 由于 nums [j] 的存在, nums [i] 一定不会是滑动窗口中的最大值了, 我们可以将 nums [i]永久地移除。
因此我们可以使用一个队列存储所有还没有被移除的下标。在队列中, 这些下标按照从小到大的顺序被存储, 并且它们在数组 nums 中对应的值是严格单调递减的。因为如果队列中有两个相邻的下标, 它们对应的值相等或者递增, 那么令前者为 $i$, 后者为 $j$, 就对应了上面所说的情况, 即 $n u m s[i]$ 会被移除,这就产生了矛盾。
当滑动窗口向右移动时, 我们需要把一个新的元素放入队列中。为了保持队列的性质, 我们会不断地将新的元素与队尾的元素相比较, 如果前者大于等于后者, 那么队尾的元素就可以被永久地移除, 我们将其弹出队列。我们需要不断地进行此项操作, 直到队列为空或者新的元素小于队尾的元素。
由于队列中下标对应的元素是严格单调递减的, 因此此时队首下标对应的元素就是滑动窗口中的最大值。同时,隨着窗口向右移动,队首元素可能会不在窗口中,我们还需要不断从队首弹出元素, 直到队首元素在窗口中为止。
1 | class Solution { |
题解(单调队列):Maximum Number of Robots Within Budget
本题相较于Sliding Window Maximum
有几点需要注意:
- 窗口大小不固定,队首弹出与budget相关而与窗口大小无关;
chargeTimes
的最值处理逻辑相同;- 求解需要知道窗口左侧的位置,需要维护窗口左侧下标。
队列中存储的还是chargeTimes
的下标,因为下标与runningCosts
一一对应,则计算总消耗时共用计算即可,本质上可以用单调队列还是因为两点,一是连续窗口,二是最值。
1 | class Solution { |
Find the Maximum Number of Marked Indices
Find the Maximum Number of Marked Indices
You are given a 0-indexed integer array nums.
Initially, all of the indices are unmarked. You are allowed to make this operation any number of times:
Pick two different unmarked indices i and j such that 2 * nums[i] <= nums[j], then mark i and j.
Return the maximum possible number of marked indices in nums using the above operation any number of times.
这题我一开始的思路是按值排序后从大到小匹配,但这样贪心还是不能获得最佳答案,需要从如何获得最优解的角度考虑。当可获得最优解时,长度为 $n$ 的数组最多只会产生 $\left\lfloor\frac{n}{2}\right\rfloor$ 对匹配, 因此对数组从小到大排序以后, 我们将数组一分为二, 左侧元素只会与右侧元素匹配。
这样操作就可以解决直接排序匹配中找不到最优配对的问题,对于右侧的一个元素,其最优配对的符合条件的元素既不是比他次大的元素,也不是全局最小的元素,而是划分成两半后左侧的符合条件的最大元素。
双指针
具体的, 我们令 $m=\left\lfloor\frac{n}{2}\right\rfloor$, 尝试将下标在 $[0, m-1]$ 范围内的元素 $n u m s[i]$ 与下标在 $[m, n-1]$ 范围内的元素 $n u m s[j]$ 进行匹配。我们从小到大枚举 $i$ ,然后找到最小的 $j$ 使其满足 $2 \times$ $n u m s[i] \leq n u m s[j]$ 。那些末满足条件而被跳过的 nums $[j]$ 将被忽略。持续这一过程,直到 $i=m$ 或 $j=n$ 。
1 | // author: SilenceZheng66 |
Count Increasing Quadruplets HARD
Count Increasing Quadruplets
Given a 0-indexed integer array nums of size n containing all numbers from 1 to n, return the number of increasing quadruplets.
A quadruplet (i, j, k, l) is increasing if:
- 0 <= i < j < k < l < n, and
- nums[i] < nums[k] < nums[j] < nums[l].
这道题直接暴力能解决一半,剩下一半学习成本有点高了,直接看灵神题解即可,现在没时间学了,感觉意义不大。
参考文献
[1] https://leetcode.cn/problems/find-the-maximum-number-of-marked-indices/solutions/2905207/qiu-chu-zui-duo-biao-ji-xia-biao-by-leet-0j2m/?envType=daily-question&envId=2024-09-12
[2] https://leetcode.cn/problems/count-increasing-quadruplets/solutions/2080632/you-ji-qiao-de-mei-ju-yu-chu-li-pythonja-exja/?envType=daily-question&envId=2024-09-10
[3] https://leetcode.cn/problems/maximum-number-of-robots-within-budget/solutions/1798725/by-endlesscheng-7ukp/?envType=daily-question&envId=2024-09-13
后记
首发于 silencezheng.top,转载请注明出处。