12. 2233. K次增加后的最大乘积(中等)
2233. K 次增加后的最大乘积 - 力扣（LeetCode）
思想
1.给你一个非负整数数组 nums 和一个整数 k 。每次操作，你可以选择 nums 中 任一 元素并将它 增加 1 。
请你返回 至多 k 次操作后，能得到的 nums的 最大乘积 。由于答案可能很大，请你将答案对 109 + 7 取余后返回。
2.贪心策略给最小的元素加1，理由如下:
以两个数a,b举例，若a>b,则a*(b+1)=ab+a>(a+1)*b=ab+b
多个数同乐
3.每次取最小元素，所以为小顶堆
代码
class Solution {
public:
typedef long long ll;
const int mod = 1e9 + 7;
int maximumProduct(vector<int>& nums, int k) {
int n = nums.size();
priority_queue<ll, vector<ll>, greater<ll>> pq(nums.begin(),
nums.end());
while (k) {
ll x = pq.top();
pq.pop();
pq.push(x + 1);
--k;
}
ll res = 1;
while (!pq.empty()) {
ll x = pq.top();
pq.pop();
res = (res * x) % mod;
}
return res;
}
};
13. 3296. 移山所需的最少秒数(中等,学习)
3296. 移山所需的最少秒数 - 力扣（LeetCode）
思想
1.给你一个整数 mountainHeight 表示山的高度。
同时给你一个整数数组 workerTimes，表示工人们的工作时间（单位：秒）。
工人们需要 同时 进行工作以 降低 山的高度。对于工人 i :
- 山的高度降低
x，需要花费workerTimes[i] + workerTimes[i] * 2 + ... + workerTimes[i] * x秒。例如：- 山的高度降低 1，需要
workerTimes[i]秒。 - 山的高度降低 2，需要
workerTimes[i] + workerTimes[i] * 2秒，依此类推。
返回一个整数，表示工人们使山的高度降低到 0 所需的 最少 秒数。
2.首先肯定是最小堆，但是按什么排序要考虑清楚，现在所有的工人是并行操作的，所以是取总的最小值，不是累加。然后能取出来说明山的高度还得降，所以要考虑该工人之前的总耗时加上当前降低山的高度1的耗时，这个总耗时最低的放在堆顶，同时也是最终答案，保证了最终答案最小。所以得知道之前总耗时和当次耗时，当次耗时可以累加基准耗时得到，所以用结构体实现。
- 山的高度降低 1，需要
代码
class Solution {
public:
typedef long long ll;
struct Node {
ll total; // 总耗时
ll next; // 下一次降低1耗时
ll base; // 基础耗时
Node(ll _total, ll _next, ll _base)
: total(_total), next(_next), base(_base) {}
};
struct cmp {
bool operator()(const Node& a, const Node& b) {
return a.total + a.next >
b.total +
b.next; // 最小堆堆顶为当前总耗时加上下一次耗时总和的最小值
}
};
priority_queue<Node, vector<Node>, cmp> pq;
long long minNumberOfSeconds(int mountainHeight, vector<int>& workerTimes) {
int n = workerTimes.size();
for (int i = 0; i < n; ++i) {
pq.push(Node(0, workerTimes[i], workerTimes[i]));
}
ll res = 0;
while (mountainHeight) {
auto tmp = pq.top();
pq.pop();
res = tmp.total + tmp.next;
pq.push(Node(res, tmp.next + tmp.base, tmp.base));
--mountainHeight;
}
return res;
}
};
14. 1942. 最小未被占据椅子的编号(中等,学习)
1942. 最小未被占据椅子的编号 - 力扣（LeetCode）
思想
1.有 n 个朋友在举办一个派对，这些朋友从 0 到 n - 1 编号。派对里有 无数 张椅子，编号为 0 到 infinity 。当一个朋友到达派对时，他会占据 编号最小 且未被占据的椅子。
- 比方说，当一个朋友到达时，如果椅子
0，1和5被占据了，那么他会占据2号椅子。
当一个朋友离开派对时，他的椅子会立刻变成未占据状态。如果同一时刻有另一个朋友到达，可以立即占据这张椅子。
给你一个下标从 0 开始的二维整数数组times，其中times[i] = [arrivali, leavingi]表示第i个朋友到达和离开的时刻，同时给你一个整数targetFriend。所有到达时间 互不相同 。
请你返回编号为targetFriend的朋友占据的 椅子编号 。
2.模拟题，首先肯定按到达时间升序遍历，当这个朋友来的时候，首先是之前的朋友的离开时间在当前朋友到达时间之前，则释放椅子，然后获得编号最小且未被占据的椅子，这个需要一个优先队列，然后再记录当前朋友的离开时间和座位号。接下来的问题就是你怎么遍历之前朋友的离开时间，然后判断是否在到达时间之前，因为也是按顺序的，所以也需要一个优先队列，按照离开时间最早的最小堆，同时要记录座位号，所以是个二元组即可。
3.模拟题先想清楚一次的流程，然后思考这次流程中需要什么数据结构，具体为数据存什么，存取数据有什么特别的顺序，最后思考多次流程的遍历顺序。
代码
class Solution {
public:
struct Node {
int idx;
int start;
int end;
Node(int _idx, int _start, int _end)
: idx(_idx), start(_start), end(_end) {}
bool operator<(const Node& other) { return start < other.start; }
};
vector<Node> vec;
typedef pair<int, int> PII;
int smallestChair(vector<vector<int>>& times, int targetFriend) {
int n = times.size();
int res = 0;
for (int i = 0; i < n; ++i) {
vec.push_back(Node(i, times[i][0], times[i][1]));
}
sort(vec.begin(), vec.end());
priority_queue<PII, vector<PII>, greater<PII>>
pqEnd; // 离开时间-座位号，离开时间最小的小根堆
priority_queue<int, vector<int>, greater<int>> pqSeat; // 座位号小根堆
for (int i = 0; i < n; ++i)
pqSeat.push(i);
for (auto& t : vec) {
// 先离开
while (!pqEnd.empty() && pqEnd.top().first <= t.start) {
pqSeat.push(pqEnd.top().second);
pqEnd.pop();
}
int res = pqSeat.top();
pqSeat.pop();
if (t.idx == targetFriend)
return res;
pqEnd.push({t.end, res});
}
return -1;
}
};
15. 1801. 积压订单中的订单总数(中等)
1801. 积压订单中的订单总数 - 力扣（LeetCode）
思想
1.给你一个二维整数数组 orders ，其中每个 orders[i] = [pricei, amounti, orderTypei] 表示有 amounti 笔类型为 orderTypei 、价格为 pricei 的订单。
订单类型 orderTypei 可以分为两种：
0表示这是一批采购订单buy1表示这是一批销售订单sell
注意，orders[i]表示一批共计amounti笔的独立订单，这些订单的价格和类型相同。对于所有有效的i，由orders[i]表示的所有订单提交时间均早于orders[i+1]表示的所有订单。
存在由未执行订单组成的 积压订单 。积压订单最初是空的。提交订单时，会发生以下情况：- 如果该订单是一笔采购订单
buy，则可以查看积压订单中价格 最低 的销售订单sell。如果该销售订单sell的价格 低于或等于 当前采购订单buy的价格，则匹配并执行这两笔订单，并将销售订单sell从积压订单中删除。否则，采购订单buy将会添加到积压订单中。 - 反之亦然，如果该订单是一笔销售订单
sell，则可以查看积压订单中价格 最高 的采购订单buy。如果该采购订单buy的价格 高于或等于 当前销售订单sell的价格，则匹配并执行这两笔订单，并将采购订单buy从积压订单中删除。否则，销售订单sell将会添加到积压订单中。
输入所有订单后，返回积压订单中的 订单总数 。由于数字可能很大，所以需要返回对109 + 7取余的结果。
2.根据题意，销售订单是小根堆，采购订单是大根堆，然后按照题意模拟，但是注意堆中元素不单单只记录价格，不然同一个价格数量太多堆中元素太多内存太大，可以存价格-数量的二元组，然后来进行数量抵消。
代码
class Solution {
public:
const int mod = 1e9 + 7;
typedef long long ll;
typedef pair<int, int> PII; // 价格-数量
int getNumberOfBacklogOrders(vector<vector<int>>& orders) {
int n = orders.size();
priority_queue<PII, vector<PII>, greater<PII>> pqSell; // 销售订单
priority_queue<PII> pqBuy; // 采购订单
for (int i = 0; i < n; ++i) {
int price = orders[i][0], amount = orders[i][1],
type = orders[i][2];
int tmp = amount;
if (type == 0) {
while (!pqSell.empty() && pqSell.top().first <= price &&
tmp > 0) {
int SellPrice = pqSell.top().first;
int cnt = pqSell.top().second;
pqSell.pop();
if (cnt > tmp) {
cnt -= tmp;
tmp = 0;
pqSell.push({SellPrice, cnt});
} else {
tmp -= cnt;
}
}
if (tmp > 0)
pqBuy.push({price, tmp});
} else {
while (!pqBuy.empty() && pqBuy.top().first >= price &&
tmp > 0) {
int BuyPrice = pqBuy.top().first;
int cnt = pqBuy.top().second;
pqBuy.pop();
if (cnt > tmp) {
cnt -= tmp;
tmp = 0;
pqBuy.push({BuyPrice, cnt});
} else {
tmp -= cnt;
}
}
if (tmp > 0)
pqSell.push({price, tmp});
}
}
ll res = 0;
while (!pqBuy.empty()) {
res = (res + pqBuy.top().second) % mod;
pqBuy.pop();
}
while (!pqSell.empty()) {
res = (res + pqSell.top().second) % mod;
pqSell.pop();
}
return res;
}
};
16. 2406. 将区间分为最少组数(中等,学习)
2406. 将区间分为最少组数 - 力扣（LeetCode）
思想
1.给你一个二维整数数组 intervals ，其中 intervals[i] = [lefti, righti] 表示 闭 区间 [lefti, righti] 。
你需要将 intervals 划分为一个或者多个区间 组 ，每个区间 只 属于一个组，且同一个组中任意两个区间 不相交 。
请你返回 最少 需要划分成多少个组。
如果两个区间覆盖的范围有重叠（即至少有一个公共数字），那么我们称这两个区间是 相交 的。比方说区间 [1, 5] 和 [5, 8] 相交。
2.首先区间肯定是按left升序排序遍历，然后利用贪心思想，要让组数更少，即让当前区间尽可能地能纳入一个组，而不是新开一个组，而纳入一个组就是要找所有组里面目前最小的right,如果left>right，则能纳入一个组里面，所以找最小的right就是最小堆，堆中每个元素就是一个组当前的right,最终堆的大小就是组的大小。
代码
class Solution {
public:
int minGroups(vector<vector<int>>& intervals) {
int n = intervals.size();
priority_queue<int, vector<int>, greater<int>> pq;
sort(intervals.begin(), intervals.end());
for (int i = 0; i < n; ++i) {
int left = intervals[i][0], right = intervals[i][1];
if (!pq.empty() && pq.top() < left)
pq.pop(); // 区间不重合，归为一组
pq.push(right);
}
return pq.size();
}
};
17. 3478. 选出和最大的K个元素(中等)
3478. 选出和最大的 K 个元素 - 力扣（LeetCode）
思想
1.给你两个整数数组，nums1 和 nums2，长度均为 n，以及一个正整数 k 。
对从 0 到 n - 1 每个下标 i ，执行下述操作：
- 找出所有满足
nums1[j]小于nums1[i]的下标j。 - 从这些下标对应的
nums2[j]中选出 至多k个，并 最大化 这些值的总和作为结果。
返回一个长度为n的数组answer，其中answer[i]表示对应下标i的结果。
2.此题首先第一个难点是" 找出所有满足nums1[j]小于nums1[i]的下标j",遍历太耗时，故而想到按照nums1[i]升序排序，在它左边的就是比它小的，因为要用下标得到nums2[j]的值，故而需要一个值-下标的二元组，而nums2[j]需要找前K大的，所以是top-k问题，使用最小堆维护。
但是一开始写完遇到一个问题，即多个nums1[i]=nums1[j]时，遍历j时最小堆里面不能纳入i，他们的答案应该一样，故想到分组循环，找到nums1[i]相等的[i,j)区间，对这个区间实施同一操作。
代码
class Solution {
public:
typedef pair<int, int> PII; // 值-下标
typedef long long ll;
vector<long long> findMaxSum(vector<int>& nums1, vector<int>& nums2,
int k) {
int n = nums1.size();
vector<long long> res(n, 0);
vector<PII> vec;
for (int i = 0; i < n; ++i) {
vec.push_back({nums1[i], i});
}
sort(vec.begin(), vec.end());
ll sum = 0;
priority_queue<int, vector<int>, greater<int>> pq;
int j = 0;
for (int i = 0; i < n; i = j) {
j = i + 1;
while (j < n && vec[i].first == vec[j].first)
++j;
ll tmp = sum;
// [i,j)
for (int z = i; z < j; ++z) {
int idx = vec[z].second;
int val = nums2[idx];
res[idx] = tmp;
pq.push(val);
sum += val;
if (pq.size() > k) {
sum -= pq.top();
pq.pop();
}
}
}
return res;
}
};
18. 2462. 雇佣K位工人的总代价(中等,左开右闭逻辑理顺,两个小根堆更快，学习)
2462. 雇佣 K 位工人的总代价 - 力扣（LeetCode）
思想
1.给你一个下标从 0 开始的整数数组 costs ，其中 costs[i] 是雇佣第 i 位工人的代价。
同时给你两个整数 k 和 candidates 。我们想根据以下规则恰好雇佣 k 位工人：
- 总共进行
k轮雇佣，且每一轮恰好雇佣一位工人。 - 在每一轮雇佣中，从最前面
candidates和最后面candidates人中选出代价最小的一位工人，如果有多位代价相同且最小的工人，选择下标更小的一位工人。- 比方说，
costs = [3,2,7,7,1,2]且candidates = 2，第一轮雇佣中，我们选择第4位工人，因为他的代价最小[_3,2_,7,7,_**1**,2_]。 - 第二轮雇佣，我们选择第
1位工人，因为他们的代价与第4位工人一样都是最小代价，而且下标更小，[_3,**2**_,7,_7,2_]。注意每一轮雇佣后，剩余工人的下标可能会发生变化。
- 比方说，
- 如果剩余员工数目不足
candidates人，那么下一轮雇佣他们中代价最小的一人，如果有多位代价相同且最小的工人，选择下标更小的一位工人。 - 一位工人只能被选择一次。
返回雇佣恰好k位工人的总代价。
2.可以用一个总堆(元素是包含下标的二元组，因为要区分处于哪个区间)或者两个小根堆(元素只有代价，更简单)模拟，然后再加上左右指针，只不过记得左指针开，右指针闭，两者处理顺序不一样
3.但是两个小根堆更好，因为堆中元素越大，push操作越慢
4.提前判断可以省很多事，通过判断candidates*2+k>n,则说明会产生元素重复，数组所有元素都要考虑，就变成求前top-k小元素的和了，同时可以省略下面idxL<idxR的判断
代码
class Solution {
public:
typedef pair<int, int> PII; // 代价-下标
typedef long long ll;
long long totalCost(vector<int>& costs, int k, int candidates) {
int n = costs.size();
ll res = 0;
priority_queue<PII, vector<PII>, greater<PII>> pq;
int idxL = candidates, idxR = n - candidates;
// [0,idxL),[idxR,n)
if (idxL < idxR) {
for (int i = 0; i < idxL; ++i)
pq.push({costs[i], i});
for (int i = idxR; i < n; ++i)
pq.push({costs[i], i});
} else {
for (int i = 0; i < n; ++i)
pq.push({costs[i], i});
}
while (k) {
auto tmp = pq.top();
pq.pop();
int cost = tmp.first, idx = tmp.second;
res += cost;
if (idxL < idxR) {
if (idx < idxL) {
pq.push({costs[idxL], idxL});
++idxL;
} else if (idx >= idxR) {
--idxR;
pq.push({costs[idxR], idxR});
}
}
--k;
}
return res;
}
};
两个小根堆:
class Solution {
public:
typedef long long ll;
long long totalCost(vector<int>& costs, int k, int candidates) {
int n = costs.size();
ll res = 0;
if (candidates * 2 + k > n) {
// 找top-k小,大根堆
priority_queue<int> pq;
for (int i = 0; i < n; ++i) {
pq.push(costs[i]);
res += costs[i];
if (pq.size() > k) {
res -= pq.top();
pq.pop();
}
}
return res;
}
int idxL = candidates, idxR = n - candidates;
priority_queue<int, vector<int>, greater<int>> pqL, pqR;
// [0,idxL),[idxR,n)
for (int i = 0; i < idxL; ++i)
pqL.push(costs[i]);
for (int i = idxR; i < n; ++i)
pqR.push(costs[i]);
while (k--) {
if (pqL.top() <= pqR.top()) {
res += pqL.top();
pqL.pop();
pqL.push(costs[idxL]);
++idxL;
} else {
res += pqR.top();
pqR.pop();
--idxR;
pqR.push(costs[idxR]);
}
}
return res;
}
};
19. 1834. 单线程CPU(中等,学习)
思想
1.给你一个二维数组 tasks ，用于表示 n 项从 0 到 n - 1 编号的任务。其中 tasks[i] = [enqueueTimei, processingTimei] 意味着第 i 项任务将会于 enqueueTimei 时进入任务队列，需要 processingTimei 的时长完成执行。
现有一个单线程 CPU ，同一时间只能执行 最多一项 任务，该 CPU 将会按照下述方式运行：
- 如果 CPU 空闲，且任务队列中没有需要执行的任务，则 CPU 保持空闲状态。
- 如果 CPU 空闲，但任务队列中有需要执行的任务，则 CPU 将会选择 执行时间最短 的任务开始执行。如果多个任务具有同样的最短执行时间，则选择下标最小的任务开始执行。
- 一旦某项任务开始执行，CPU 在 执行完整个任务 前都不会停止。
- CPU 可以在完成一项任务后，立即开始执行一项新任务。
返回 CPU 处理任务的顺序。
2.首先这题不能按照任务来遍历(注意，卡了好久)，因为CPU是一空闲就会取下一个待执行的任务执行，而不会等到下一个遍历的任务来。
其次，不能按照时间累加遍历，因为太慢了，会超时。
所以时间得跳着来。 - (1)当前无任务队列，时间跳到下一个待遍历的任务
- (2)当前有任务队列，则取出完成，然后时间直接跳到完成时间
- (3)任务首先入队列，因为时间是跳着来的，(2)的情况可能会有多个任务入队列，所以要用
while循环
代码
class Solution {
public:
typedef long long ll;
struct Node {
int start;
int last;
int idx;
Node(int _start, int _last, int _idx)
: start(_start), last(_last), idx(_idx) {}
bool operator<(const Node& other) { return start < other.start; }
};
struct cmp {
bool operator()(const Node& a, const Node& b) {
if (a.last != b.last)
return a.last > b.last;
else
return a.idx > b.idx;
}
};
priority_queue<Node, vector<Node>, cmp> pq;
vector<Node> vec;
vector<int> getOrder(vector<vector<int>>& tasks) {
int n = tasks.size();
vector<int> res;
for (int i = 0; i < n; ++i)
vec.push_back(Node(tasks[i][0], tasks[i][1], i));
sort(vec.begin(), vec.end());
ll time = 0, i = 0;
while (res.size() < n) {
// time是跳跃的，所以可能之前有好多任务要入
while (i < n && vec[i].start <= time) {
pq.push(vec[i]);
++i;
}
// 跳到下一个任务的入队时间
if (pq.empty()) {
time = vec[i].start;
} else {
auto tmp = pq.top();
pq.pop();
res.push_back(tmp.idx);
time += 1LL * tmp.last; // 跳到结束时间
}
}
return res;
}
};