文章目录
- Tag
- 题目来源
- 解题思路
- 方法一:贪心+优先队列
- 写在最后
Tag
【贪心+优先队列】【数组】【2023-12-23】
题目来源
1962. 移除石子使总数最小
解题思路
方法一:贪心+优先队列
思路
本题比较简单,思路也十分清晰。对于 k 次操作,每次操作只需要从数组 piles
中贪心的选取当前最大的整数,对其取下整操作即可。
算法
class Solution {
public:
int minStoneSum(vector<int>& piles, int k) {
priority_queue<int> pq(piles.begin(), piles.end());
for (int i = 0; i < k; ++i) {
int pile = pq.top();
pq.pop();
pile -= pile / 2;
pq.push(pile);
}
int sum = 0;
while (!pq.empty()) {
sum += pq.top();
pq.pop();
}
return sum;
}
};
复杂度分析
时间复杂度:
O
(
k
×
l
o
g
n
+
n
)
O(k \times logn + n)
O(k×logn+n),
n
n
n 是数组 piles
的长度。将数组变成优先队列消耗
O
(
n
)
O(n)
O(n),k
次入队和出队的操作,每次消耗
O
(
l
o
g
n
)
O(logn)
O(logn),总的时间复杂度为
O
(
k
×
l
o
g
n
+
n
)
O(k \times logn + n)
O(k×logn+n)。
空间复杂度: O ( n ) O(n) O(n),新建优先队列消耗的空间。
写在最后
如果您发现文章有任何错误或者对文章有任何疑问,欢迎私信博主或者在评论区指出 💬💬💬。
如果大家有更优的时间、空间复杂度的方法,欢迎评论区交流。
最后,感谢您的阅读,如果有所收获的话可以给我点一个 👍 哦。