308 字
2 分钟
算法 : 堆
手写堆:
void up(int x) { while (x > 1 && h[x] > h[x / 2]) { std::swap(h[x], h[x / 2]); x /= 2; }}
void down(int x) { while (x * 2 <= n) { int t = x * 2; if (t + 1 <= n && h[t + 1] > h[t]) t++; if (h[t] <= h[x]) break; std::swap(h[x], h[t]); x = t; }}
void build_heap_1() { for (int i = 1; i <= n; i++) up(i);}
void build_heap_2() { for (int i = n; i >= 1; i--) down(i);}基础
- 1046. 最后一块石头的重量 - 力扣（LeetCode）
- 3264. K 次乘运算后的最终数组 I - 力扣（LeetCode）
- 2558. 从数量最多的堆取走礼物 - 力扣（LeetCode）
- 2336. 无限集中的最小数字 - 力扣（LeetCode）
- 2530. 执行 K 次操作后的最大分数 - 力扣（LeetCode）
- 3066. 超过阈值的最少操作数 II - 力扣（LeetCode）
- 1962. 移除石子使总数最小 - 力扣（LeetCode）
- 703. 数据流中的第 K 大元素 - 力扣（LeetCode）
第K大:
class KthLargest { priority_queue<int, vector<int>, greater<int>> pque; int k;
public: KthLargest(int k, vector<int>& nums) : k(k) { for (int x : nums) { pque.push(x); if (pque.size() > k) { pque.pop(); } } }
int add(int val) { pque.push(val); if (pque.size() > k) { pque.pop(); }
return pque.top(); }};