题目链接：合并 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) {
        vector<int> nodes;
        for (int i = 0;i < lists.size();i++) {
            ListNode* cur = lists[i];
            while (cur != nullptr) {
                nodes.push_back(cur->val);
                cur = cur->next;
            }
        }
        sort(nodes.begin(),nodes.end());

        ListNode head(0);
        ListNode* tmp = &head;
        //tmp = nullptr;
        //head->next = tmp;
        for (int i = 0;i < nodes.size();i++) {
            tmp->next = new ListNode(nodes[i]);
            tmp = tmp->next;
        }
        return head.next;
    }
};

题目链接：K 个一组翻转链表

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

方法一：链表反转

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        // 统计节点个数
        int n = 0;
        for (ListNode* cur = head; cur; cur = cur->next) {
            n++;
        }

        ListNode dummy(0, head);
        ListNode* p0 = &dummy;
        ListNode* pre = nullptr;
        ListNode* cur = head;

        // k 个一组处理
        for (; n >= k; n -= k) {
            for (int i = 0; i < k; i++) { // 同 92 题
                ListNode* nxt = cur->next;
                cur->next = pre; // 每次循环只修改一个 next，方便大家理解
                pre = cur;
                cur = nxt;
            }

         
            ListNode* nxt = p0->next; // p0->next 是小循环最后一个节点 （即开头的第一个节点，反转后变成小循环最后一个节点）
            p0->next->next = cur; // cur 是下一个循环开始 ，把本次循环最后一个节点（p0->next）连接新一轮循环
            p0->next = pre; //把p0->next 指向反转后的第一个节点（反转前的最后一个节点）用来连接旧循环和本次循环
            p0 = nxt; // p0变成本次循环最后一个点 即新循环上一个点
        }
        return dummy.next;
    }
};

题目链接：二叉树中的最大路径和

二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

方法一：递归

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int dfs(TreeNode* root,int &ans) {
        if (root == nullptr) return 0;
        int l_val = dfs(root->left,ans);
        int r_val = dfs(root->right,ans);
        ans = max(ans,l_val+r_val+root->val);
        return max(max(l_val,r_val) + root->val,0);
    }
    int maxPathSum(TreeNode* root) {
        int ans = INT_MIN;
        dfs(root,ans);
        return ans;
    }
};

题目链接：数据流的中位数

中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

• 例如 arr = [2,3,4] 的中位数是 3 。
• 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。

实现 MedianFinder 类:

• MedianFinder() 初始化 MedianFinder 对象。
• void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
• double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。

方法一：堆

class MedianFinder {
public:
    priority_queue<int, vector<int>, greater<int>> A; // 小顶堆，保存较大的一半
    priority_queue<int, vector<int>, less<int>> B; // 大顶堆，保存较小的一半
    MedianFinder() { }
    void addNum(int num) {
        if (A.size() != B.size()) {
            A.push(num);
            B.push(A.top());
            A.pop();
        } else {
            B.push(num);
            A.push(B.top());
            B.pop();
        }
    }
    double findMedian() {
        return A.size() != B.size() ? A.top() : (A.top() + B.top()) / 2.0;
    }
};

题目链接：柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

方法一：单调栈

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        heights.insert(heights.begin(),0);
        heights.push_back(0);
        stack<int> s;
        int res = 0;
        for (int i = 0;i < heights.size();i++) {
            while (s.size() && heights[s.top()] > heights[i]) {
                int cur = s.top();
                s.pop();
                res = max(res,(i - 1 - s.top()) * heights[cur]);
            }
            s.push(i);
        }
        return res;
    }
};