11.5 优先队列
Input: [73, 74, 75, 71, 69, 72, 76, 73] Output: [1, 1, 4, 2, 1, 1, 0, 0]
pp qqqpq
pp
vector<int> dailyTemperatures(vector<int>& temperatures) { int n = temperatures.size();
vector<int> ans(n);
stack<int> indices;
for (int i = 0; i < n; ++i) { while (!indices.empty()) {
int pre_index = indices.top();
if (temperatures[i] <= temperatures[pre_index]) { break;
} indices.pop();
ans[pre_index] = i - pre_index;
} indices.push(i);
} return ans;
}
11.5
priority queueO¹1ºO¹log nº
heap
ii/2 2i2i+1

11.2:
vector<int> heap;
// void top() {
return heap[0];
}
// void push(int k) {
heap.push_back(k);
swim(heap.size() - 1);
}
// void pop() {
heap[0] = heap.back();
heap.pop_back();
sink(0);
}
// void swim(int pos) {
while (pos > 1 && heap[pos/2] < heap[pos])) { swap(heap[pos/2], heap[pos]);
pos /= 2;
} }
// void sink(int pos) {
while (2 * pos <= N) { int i = 2 * pos;
if (i < N && heap[i] < heap[i+1]) ++i;
if (heap[pos] >= heap[i]) break;
swap(heap[pos], heap[i]);
pos = i;
STL
23. Merge k Sorted Lists (Hard)
k
Input:
[1->4->5, 1->3->4,
2->6] Output: 1->1->2->3->4->4->5->6
Comp
operator()
struct Comp { bool operator() (ListNode* l1, ListNode* l2) {
return l1->val > l2->val;
} };
ListNode* mergeKLists(vector<ListNode*>& lists) { if (lists.empty()) return nullptr;
priority_queue<ListNode*, vector<ListNode*>, Comp> q;
for (ListNode* list: lists) { if (list) {
q.push(list);
} }
ListNode* dummy = new ListNode(0), *cur = dummy;
while (!q.empty()) { cur->next = q.top();
q.pop();
cur = cur->next;
if (cur->next) { q.push(cur->next);
return dummy->next;
218. The Skyline Problem (Hard)
[,,]

11.3:218 -
Input: [[2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8]] Output: [[2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0]]
pair
vector<vector<int>> getSkyline(vector<vector<int>>& buildings) { vector<vector<int>> ans;
priority_queue<pair<int, int>> max_heap; // <,> int i = 0, len = buildings.size();
int cur_x, cur_h;
while (i < len || !max_heap.empty()) { if (max_heap.empty() || i < len && buildings[i][0] <= max_heap.top().
second) { cur_x = buildings[i][0];
while (i < len && cur_x == buildings[i][0]) { max_heap.emplace(buildings[i][2], buildings[i][1]);
++i;
} } else {
cur_x = max_heap.top().second;
while (!max_heap.empty() && cur_x >= max_heap.top().second) { max_heap.pop();
全站分卷索引 · 68 卷
- 11 题目分类
- 22 最易懂的贪心算法
- 32.3 区间问题
- 42.4 练习
- 53 玩转双指针
- 63.2 Two Sum
- 73.4 快慢指针
- 83.5 滑动窗口
- 93.6 练习
- 104 居合斩!二分查找
- 114.3 查找区间
- 124.4 旋转数组查找数字
- 134.5 练习
- 145 千奇百怪的排序算法
- 155.2 快速选择
- 165.3 桶排序
- 175.4 练习
- 186 一切皆可搜索
- 196.3 回溯法
- 206.4 广度优先搜索
- 216.5 练习
- 227 深入浅出动态规划
- 237.3 基本动态规划:二维
- 247.4 分割类型题
- 257.5 子序列问题
- 267.6 背包问题
- 277.7 字符串编辑
- 287.8 股票交易
- 297.9 练习
- 308 化繁为简的分治法
- 318.3 练习
- 329 巧解数学问题
- 339.4 数字处理
- 349.5 随机与取样
- 359.6 练习
- 3610 神奇的位运算
- 3710.3 二进制特性
- 3810.4 练习
- 3911 妙用数据结构
- 4011.2 数组
- 4111.3 栈和队列
- 4211.4 单调栈
- 4311.5 优先队列
- 4411.6 双端队列
- 4511.7 哈希表
- 4611.8 多重集合和映射
- 4711.9 前缀和与积分图
- 4811.10 练习
- 11.10
- 566. Reshape the Matrix (Easy)
- 225. Implement Stack using Queues (Easy)
- 503. Next Greater Element II (Medium)
- 217. Contains Duplicate (Easy)
- 697. Degree of an Array (Easy)
- 594. Longest Harmonious Subsequence (Easy)
- 287. Find the Duplicate Number (Medium)
- 313. Super Ugly Number (Medium)
- 870. Advantage Shuffle (Medium)
- 307. Range Sum Query - Mutable (Medium)
- 4912 令人头大的字符串
- 5012.3 字符串理解
- 5112.4 字符串匹配
- 5212.5 练习
- 5313 指针三剑客之一:链表
- 5413.3 其它链表技巧
- 5513.4 练习
- 5614 指针三剑客之二:树
- 5714.3 层次遍历
- 5814.4 前中后序遍历
- 5914.5 二叉查找树
- 6014.6 字典树
- 6114.7 练习
- 14.7
- 226. Invert Binary Tree (Easy)
- 617. Merge Two Binary Trees (Easy)
- 572. Subtree of Another Tree (Easy)
- 404. Sum of Left Leaves (Easy)
- 513. Find Bottom Left Tree Value (Easy)
- 538. Convert BST to Greater Tree (Easy)
- 235. Lowest Common Ancestor of a Binary Search Tree (Easy)
- 530. Minimum Absolute Difference in BST (Easy)
- 889. Construct Binary Tree from Preorder and Postorder Traversal (Medium)
- 106. Construct Binary Tree from Inorder and Postorder Traversal (Medium)
- 94. Binary Tree Inorder Traversal (Medium)
- 6215 指针三剑客之三:图
- 6315.3 拓扑排序
- 6415.4 练习
- 6516 更加复杂的数据结构
- 6616.3 复合数据结构
- 6716.4 练习
- 6817 后记