给定一个链表数组，每个链表都已经按升序排列。请将所有链表合并到一个升序链表中，返回合并后的链表。

输入是一个一维数组，每个位置存储链表的头节点；输出是一条链表。

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组：[1->4->5, 1->3->4, 2->6] 将它们合并到一个有序链表中得到：1->1->2->3->4->4->5->6

解析：

​ 本题我们可以采用STL中的容器适配器 priority_queue，把所有的链表存储在一个优先队列中，每次提取所有链表头部节点值最小的那个节点，直到所有链表都被提取完为止。

​ 需要注意的是 priority_queue 默认的元素比较方法是less<T>，即默认为最大值元素在前面的最大堆，维持着递增关系。如果我们想要获取最小的节点值，则需要实现一个最小堆，因此比较函数应该维持递减关系。实现侧策略就是使用函数对象，自定义 priority_queue 的元素比较方法，在该函数对象中重载 operator() ，使用大于号而不是等增关系时的小于号进行比较。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/struct MyCompare{bool operator() (ListNode* a, ListNode* b){return a->val > b->val;}
};class Solution {
public:ListNode* mergeKLists(vector<ListNode*>& lists) {if(lists.empty()) return nullptr;// 自定义优先队列的元素比较方法 MyComparepriority_queue<ListNode*, vector<ListNode*>, MyCompare> pq;// 将lists都压入到优先队列中，保持递减关系for(const auto list: lists){if(list){pq.push(list);}}// 每次取出所有链表中头部节点最小的那个节点加入结果链表ListNode head; ListNode* tail = &head;while(!pq.empty()){// 取出所有链表中的最小头节点并加入 结果链表tail->next = pq.top();pq.pop();tail = tail->next;// 加入后，将其 next 节点作为当前链表的新头节点加入优先队列if(tail->next){pq.push(tail->next);}}return head.next;}
};

本题也可以采用归并排序的思想，将链表两两合并。

根据分治策略，首先要将 k 个链表分割，使用递归的方法将链表分割为两两一组。然后将在同一个组的链表合并。

合并两个有序链表可以通过如下操作实现：

• 首先需要一个变量 head 来保存合并之后链表的头部，在整个链表合并完之后，返回 head 的下一位置即可。
• 需要一个指针 tail 来记录下一个插入位置的前一个位置，以及两个指针 aPtr 和 bPtr 来记录 a 和 b 未合并部分的第一位，即通过尾插法构建新链表
• 当 aPtr 和 bPtr 都不为空的时候，取 val 熟悉较小的合并；如果 aPtr 为空，则把整个 bPtr 以及后面的元素全部合并；bPtr 为空时同理。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* mergeTowList(ListNode* a, ListNode* b){if(!a || !b) return a?a:b;// 变量 head 来保存合并之后链表的头部ListNode head;ListNode* tail = &head;ListNode* aPtr = a;ListNode* bPtr = b;while(aPtr && bPtr){if(aPtr->val <= bPtr->val){tail->next = aPtr;aPtr = aPtr->next;}else{tail->next = bPtr;bPtr = bPtr->next;}tail = tail->next;}// 循环结束 aPtr 和 bPtr 其中一个为空，直接将非空的添加到链表if(aPtr){tail->next = aPtr;}else{tail->next = bPtr;}return head.next;}ListNode* merge(vector<ListNode*>& lists, int lsh, int rsh){if(lsh == rsh){return lists[lsh];}if(lsh > rsh){return nullptr;}int mid = (lsh + rsh) >> 1;ListNode* lshList = merge(lists,lsh,mid);ListNode* rshList = merge(lists,mid+1,rsh);return mergeTowList(lshList,rshList);}ListNode* mergeKLists(vector<ListNode*>& lists) {return merge(lists,0,lists.size()-1);}
};

给定建筑物的起止位置和高度，返回建筑物轮廓（天际线）的拐点。

输入是一个二维整数数组，表示每个建筑物的 [左端, 右端, 高度]；输出是一个二维整数数组，表示每个拐点的横纵坐标。

输入：buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
输出：[[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
解释：图 A 显示输入的所有建筑物的位置和高度，图 B 显示由这些建筑物形成的天际线。图 B 中的红点表示输出列表中的关键点。

解析：

​ 本题没搞懂，有待再理解

​ 我们可以使用优先队列储存每个建筑物的高度和右端（这里使用 pair，其默认比较函数是先比较第一个值，如果相等则再比较第二个值），从而获取目前会拔高天际线、且妨碍到前一个建筑物（的右端端点）的下一个建筑物。

class Solution {
public:vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {vector<vector<int>> ans;priority_queue<pair<int,int>> heap;int i = 0;int len = buildings.size();int cur_x, cur_h;while(i<len || !heap.empty()){if(heap.empty() || i<len && buildings[i][0] <= heap.top().second){cur_x = buildings[i][0];while(i<len && cur_x==buildings[i][0]){heap.emplace(buildings[i][2], buildings[i][1]);++i;}}else{cur_x = heap.top().second;while(!heap.empty() && cur_x >= heap.top().second){heap.pop();}}cur_h = (heap.empty())?0:heap.top().first;if(ans.empty() || cur_h != ans.back()[1]){ans.push_back({cur_x,cur_h});}}return ans;}
};

给定两个大小相等的数组 A 和 B，A 相对于 B 的优势可以用满足 A[i] > B[i] 的索引 i 的数目来描述。

返回 A 的任意排列，使其相对于 B 的优势最大化。

输入：A = [12,24,8,32], B = [13,25,32,11]
输出：[24,32,8,12]

解析：

​ 本题采用田忌赛马的策略，如果 A 中有元素比 B 的大，那么用最大的那个值取对应B中的元素；如果A中没有元素比当前B大，那么用最小的 A 对应该元素。

​ 我们采用优先队列保存 B 中的元素值和原先位置，并维持递减顺序。将 A 中元素按递增排序，然后遍历优先队列中的 B 元素。因为B采用优先队列保存，所以取出的总是当前B的最大元素，如果 A 中存在比该元素还大的值，则取 A 的当前最大值即排序后数组末尾元素放在该元素的原先位置；不存在就用 A 中的最小元素即排序后数组第一个元素放在该元素的原先位置。

​ 例如A = [12,24,8,32], B = [13,25,32,11]，对A排序，对B用优先队列存储元素值和原先位置有A = [8,12,24,32], B = [{32,2},{25,1},{13,0},{11,3}]，结果形成过程如下：

class Solution {
public:vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {vector<int> ans(nums1.size());// A 排序sort(nums1.begin(),nums1.end());// B 用优先队列保存priority_queue<pair<int,int>> pq;for(int i=0;i<nums2.size();++i){pq.push(make_pair(nums2[i],i));}// 逐个比较优先队列中的元素，根据大取大、小取小的原则洗牌A的元素int head = 0, tail = nums1.size()-1;while(!pq.empty()){int num = pq.top().first;int index = pq.top().second;pq.pop();if(nums1[tail]>num){ans[index] = nums1[tail--];}else{ans[index] = nums1[head++];}}return ans;}
};