LCR 078. 合并 K 个升序链表

既然每个链表都是升序的，那么合并后的第一个节点一定是某个链表的头节点

合并后的第二个节点，可能是某个链表的头节点，也可能是第一个节点的下一个节点

所以我们需要把所有可能是下一个节点的节点放在一个集合中，并且最小的可以自动浮起来，即最小堆

/**
 * 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* mergeKLists(vector<ListNode*>& lists) {
        struct Comparator {  
            bool operator()(ListNode *a, ListNode *b) {
                return a->val > b->val; //代表小根堆，因为如果返回true，就表示左侧元素的优先级低于右侧元素(有点反直觉)
            }
        };
        priority_queue<ListNode*, vector<ListNode* >, Comparator> pq;
        // 先把每个链表的头节点都放进去
        for(auto head : lists) {
            if(head) pq.push(head);
        }
        ListNode* dummy = new ListNode();
        ListNode* cur = dummy;
        while(!pq.empty()) {
            ListNode* node = pq.top(); // 把最小的取出来
            pq.pop();
            cur->next = node;
            cur = cur->next;
            if(node->next) pq.push(node->next);
        }
        return dummy->next;
    }
};

41. 缺失的第一个正数

不能排序，不能开数组，只能用排排队的思路，每个人都必须坐在属于自己的位子上

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        for(int i = 0; i < nums.size(); i++) {
            if(nums[i] < 0 || nums[i] > nums.size()) nums[i] = 0;
        }

        for(int i = 0; i < nums.size(); i++) {
            if(nums[i] && nums[i] != i + 1) { //如果坐错了位置
                int tmp = nums[i]; //坐错的人先站一边去 
                nums[i] = 0; //那么位置就空了
                while(tmp > 0 && nums[tmp - 1] != tmp) { //去找属于自己的位置 tmp>0保证索引合法
                    if(!nums[tmp - 1]) {
                        nums[tmp - 1] = tmp; //正确的位置是空的 直接坐下
                    } else { //已经有人了
                        int ta = nums[tmp - 1]; //让他离开
                        nums[tmp - 1] = tmp; //tmp坐下
                        tmp = ta; //ta变成新的tmp 去找正确的座位
                    }
                }
            }
        }
        int i = 0;
        for(i = 0; i < nums.size() && nums[i]; i++);  
        //i号位置是空的 说明i+1号乘客不在
        //如果每个人都坐对了 那么返回nums.size()+1 符合题意
        return i + 1;
    }
};

1944. 队列中可以看到的人数

单调栈：从后往前遍历，维护一个从栈底到栈顶单调递减的序列，即维护没有被挡住的人的位置。

如果左边的能挡住右边的，就弹出右边，因为看不到他了，保持身高单调递减。

若heights[i]大于栈顶元素，就不断弹出并计数（直到栈顶元素大于heights[i]或者栈空），作为它能看到的人数。

class Solution {
public:
    vector<int> canSeePersonsCount(vector<int>& heights) {
        stack<int> sk; // 维护单调递减栈
        vector<int> res(heights.size(), 0);
        for(int i = heights.size() - 1; i >= 0; i--) {
            int cnt = 0;
            while(!sk.empty() && heights[i] > heights[sk.top()]) {
                sk.pop(); // 如果左边的能挡住右边的 就弹出右边 因为看不到他了
                cnt++; // 也就是说 若heights[i]大于栈顶元素 就不断弹出并计数 作为它能看到的人数
            }
            if(!sk.empty()) cnt++;
            sk.push(i);
            res[i] = cnt;
        }
        return res;
    }
};