leetcode——栈、队列、优先队列

左手的ㄟ右手 2022-10-13 12:35 192阅读 0赞

### 题目 ###

*   *  20. 有效的括号
     *  150. 逆波兰表达式求值
     *  71. 简化路径
     *  144. 二叉树的前序遍历
     *  94. 二叉树的中序遍历
     *  145. 二叉树的后序遍历
     *  341. 扁平化嵌套列表迭代器
     *  102. 二叉树的层序遍历
     *  107. 二叉树的层序遍历 II
     *  103. 二叉树的锯齿形层序遍历
     *  199. 二叉树的右视图
     *  347. 前 K 个高频元素
     *  23. 合并K个升序链表

## 20. 有效的括号 ##

给定一个只包括 ‘(’，’)’，’\{’，’\}’，’\[’，’\]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
    左括号必须以正确的顺序闭合。

示例 1：

输入：s = “()”  
输出：true

示例 2：

输入：s = “()\[\]\{\}”  
输出：true

示例 3：

输入：s = “(\]”  
输出：false

示例 4：

输入：s = “(\[)\]”  
输出：false

示例 5：

输入：s = “\{\[\]\}”  
输出：true

提示：

1 <= s.length <= 104
    s 仅由括号 '()[]{}' 组成

题解：经典的括号匹配问题，用栈处理。

那么这里为什么不用Stack，而使用ArrayDeque呢？因为Stack是Vector的子类，而Vector里面的方法基本都是用synchronized修饰的，虽然是线程安全的，但是效率会比较低，而对于ArrayList和ArrayDeque，本身是线程不安全的，若想要线程安全，只需使用Collections.synchronizedCollection()转化成线程安全的,基本可以绕过Vector。

class Solution {
        
        public boolean isValid(String s) {
        
            char[] sc = s.toCharArray();
            ArrayDeque<Character> deque = new ArrayDeque();
            for(int i = 0; i < sc.length; i++){
        
                if(sc[i] == '(' || sc[i] == '[' || sc[i] == '{'){
        
                    deque.addLast(sc[i]);
                }else{
        
                    if(deque.isEmpty()){
        
                        return false;
                    }
                    char c = deque.removeLast();
                    if((sc[i] == ')' && c != '(' ) || (sc[i] == '}' && c != '{' ) || (sc[i] == ']' && c != '[' ))
                    return false;
                }
            }
            return deque.isEmpty();
        }
    }

## 150. 逆波兰表达式求值 ##

根据 逆波兰表示法，求表达式的值。

有效的算符包括 +、-、\*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：

整数除法只保留整数部分。
    给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

示例 1：

输入：tokens = \[“2”,“1”,"+",“3”,"\*"\]  
输出：9  
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) \* 3) = 9

示例 2：

输入：tokens = \[“4”,“13”,“5”,"/","+"\]  
输出：6  
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

示例 3：

输入：tokens = \[“10”,“6”,“9”,“3”,"+","-11","*","/","*",“17”,"+",“5”,"+"\]  
输出：22  
解释：  
该算式转化为常见的中缀算术表达式为：  
((10 \* (6 / ((9 + 3) \* -11))) + 17) + 5  
= ((10 \* (6 / (12 \* -11))) + 17) + 5  
= ((10 \* (6 / -132)) + 17) + 5  
= ((10 \* 0) + 17) + 5  
= (0 + 17) + 5  
= 17 + 5  
= 22

提示：

1 <= tokens.length <= 104
    tokens[i] 要么是一个算符（"+"、"-"、"*" 或 "/"），要么是一个在范围 [-200, 200] 内的整数

逆波兰表达式：

逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
    该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点：

去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
    适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。

题解：上面介绍优点的第二个就是题解。

class Solution {
        
        public int evalRPN(String[] tokens) {
        
            ArrayDeque<Integer> deque = new ArrayDeque();
            for(int i = 0; i < tokens.length; i++){
        
                if(isNumber(tokens[i])){
        
                    deque.addLast(Integer.parseInt(tokens[i]));
                }else{
        
                    Integer a = deque.removeLast();
                    Integer b = deque.removeLast();
                    switch(tokens[i]){
        
                        case "+" : deque.addLast(b + a); break;
                        case "-" : deque.addLast(b - a); break;
                        case "*" : deque.addLast(b * a); break;
                        case "/" : deque.addLast(b / a); break;
                    }
                }
            }
            return deque.removeLast(); 
        }
    
        public boolean isNumber(String str){
        
            return !(str.equals("+") || str.equals("-") || str.equals("*") || str.equals("/"));
        }
    }

## 71. 简化路径 ##

给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 ‘/’ 开头），请你将其转化为更加简洁的规范路径。

在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （…） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，’//’）都被视为单个斜杠 ‘/’ 。 对于此问题，任何其他格式的点（例如，’…’）均被视为文件/目录名称。

请注意，返回的 规范路径 必须遵循下述格式：

始终以斜杠 '/' 开头。
    两个目录名之间必须只有一个斜杠 '/' 。
    最后一个目录名（如果存在）不能 以 '/' 结尾。
    此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 '.' 或 '..'）。

返回简化后得到的 规范路径 。

示例 1：

输入：path = “/home/”  
输出："/home"  
解释：注意，最后一个目录名后面没有斜杠。

示例 2：

输入：path = “/…/”  
输出："/"  
解释：从根目录向上一级是不可行的，因为根目录是你可以到达的最高级。

示例 3：

输入：path = “/home//foo/”  
输出："/home/foo"  
解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。

示例 4：

输入：path = “/a/./b/…/…/c/”  
输出："/c"

提示：

1 <= path.length <= 3000
    path 由英文字母，数字，'.'，'/' 或 '_' 组成。
    path 是一个有效的 Unix 风格绝对路径。

题解：将字符串按照 “/”分隔开，然后遍历，过滤掉空格和“.”,如果是“. .”，并且栈不为空，则出栈；否则入栈。

class Solution {
        
        public String simplifyPath(String path) {
        
            String[] res = path.split("/");
            ArrayDeque<String> deque = new ArrayDeque();
            for(int i = 0; i < res.length; i++){
        
                if(!res[i].equals("") && !res[i].equals(".")){
        
                    if(res[i].equals("..")){
        
                        if(!deque.isEmpty())
                            deque.removeLast();
                    }else{
        
                        deque.addLast(res[i]);
                    }
                }
            }
            StringBuilder sb = new StringBuilder();
            for(String s : deque){
        
                sb.append("/" + s);
            }
            if(sb.toString().equals(""))
                return "/";
            return sb.toString();
        }
    }

## 144. 二叉树的前序遍历 ##

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

示例 1：  
![在这里插入图片描述][2021070623290088.png]

输入：root = \[1,null,2,3\]  
输出：\[1,2,3\]

示例 2：

输入：root = \[\]  
输出：\[\]

示例 3：

输入：root = \[1\]  
输出：\[1\]

示例 4：  
![在这里插入图片描述][202107062329139.png]

输入：root = \[1,2\]  
输出：\[1,2\]

示例 5：

输入：root = \[1,null,2\]  
输出：\[1,2\]

提示：

树中节点数目在范围 [0, 100] 内
    -100 <= Node.val <= 100

进阶：递归算法很简单，你可以通过迭代算法完成吗？

①递归实现：

②迭代实现：对于二叉树的前序遍历，可以先推根节点入栈，进入循环，因为栈是后入先出，所以先推入右节点，后推入左节点。

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        
        public List<Integer> preorderTraversal(TreeNode root) {
        
            ArrayDeque<TreeNode> deque = new ArrayDeque<>();
            List<Integer> res = new ArrayList<>();
            if(root == null)
                return res;
            deque.addLast(root);
            while(!deque.isEmpty()){
        
                TreeNode node = deque.removeLast();
                res.add(node.val);
                if(node.right != null){
        
                    deque.addLast(node.right);
                }
                if(node.left != null){
        
                    deque.addLast(node.left);
                }
            }
            return res;
        }   
    }

## 94. 二叉树的中序遍历 ##

给定一个二叉树的根节点 root ，返回它的 中序 遍历。

示例 1：

输入：root = \[1,null,2,3\]  
输出：\[1,3,2\]

示例 2：

输入：root = \[\]  
输出：\[\]

示例 3：

输入：root = \[1\]  
输出：\[1\]

示例 4：

输入：root = \[1,2\]  
输出：\[2,1\]

示例 5：

输入：root = \[1,null,2\]  
输出：\[1,2\]

提示：

树中节点数目在范围 [0, 100] 内
    -100 <= Node.val <= 100

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

递归：

迭代实现思路：用栈，一路找到二叉树的最左孩子，弹出并存入结果；然后判断当前节点有无右节点，有的话需要继续找到其最左孩子。

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        
        public List<Integer> inorderTraversal(TreeNode root) {
        
            ArrayDeque<TreeNode> deque = new ArrayDeque<>();
            List<Integer> res = new ArrayList<>();
            if(root == null)
                return res;
            TreeNode cur = root;
            while(!deque.isEmpty() || cur != null){
        
                while(cur != null){
        
                    deque.addLast(cur);
                    cur = cur.left;
                }
                TreeNode node = deque.removeLast();
                res.add(node.val);
                if(node.right != null){
        
                    cur = node.right;
                }
            }
            return res;
        }
    }

## 145. 二叉树的后序遍历 ##

给定一个二叉树，返回它的 后序 遍历。

示例:

输入: \[1,null,2,3\]  
1  
  
2  
/  
3

输出: \[3,2,1\]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

递归：

迭代：后序遍历打印的结果是左右中，所以我们入栈的顺序可以是中右左。

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        
        public List<Integer> postorderTraversal(TreeNode root) {
        
            ArrayDeque<TreeNode> deque = new ArrayDeque<>();
            ArrayDeque<Integer> resDeque = new ArrayDeque<>();
            List<Integer> res = new ArrayList<>();
            if(root == null)
                return res;
            deque.addLast(root);
            while(!deque.isEmpty()){
        
                TreeNode node = deque.removeLast();
                resDeque.addLast(node.val);
                if(node.left != null)
                    deque.addLast(node.left);
                if(node.right != null)
                    deque.addLast(node.right);
            }
            while(!resDeque.isEmpty()){
        
                res.add(resDeque.removeLast());
            }
            return res;
        }
    }

## 341. 扁平化嵌套列表迭代器 ##

给你一个嵌套的整型列表。请你设计一个迭代器，使其能够遍历这个整型列表中的所有整数。

列表中的每一项或者为一个整数，或者是另一个列表。其中列表的元素也可能是整数或是其他列表。

示例 1:

输入: \[\[1,1\],2,\[1,1\]\]  
输出: \[1,1,2,1,1\]  
解释: 通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: \[1,1,2,1,1\]。

示例 2:

输入: \[1,\[4,\[6\]\]\]  
输出: \[1,4,6\]  
解释: 通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: \[1,4,6\]。

思路：把一个嵌套的列表，存储到普通列表中，然后实现iterator()方法。

/**
     * // This is the interface that allows for creating nested lists.
     * // You should not implement it, or speculate about its implementation
     * public interface NestedInteger {
     *
     *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
     *     public boolean isInteger();
     *
     *     // @return the single integer that this NestedInteger holds, if it holds a single integer
     *     // Return null if this NestedInteger holds a nested list
     *     public Integer getInteger();
     *
     *     // @return the nested list that this NestedInteger holds, if it holds a nested list
     *     // Return empty list if this NestedInteger holds a single integer
     *     public List<NestedInteger> getList();
     * }
     */
    public class NestedIterator implements Iterator<Integer> {
        
        private List<Integer> list;
        private Iterator<Integer> cur;
    
        public NestedIterator(List<NestedInteger> nestedList) {
        
            list = new ArrayList<>();
            // 把值传入list
            DFS(nestedList);
            cur = list.iterator();    
        }
    
        @Override
        public Integer next() {
        
            return cur.next();
        }
    
        @Override
        public boolean hasNext() {
        
            return cur.hasNext();
        }
    
        public void DFS(List<NestedInteger> nestedList){
        
            for(NestedInteger i : nestedList){
        
                if(i.isInteger()){
        
                    list.add(i.getInteger());
                }else{
        
                    DFS(i.getList());
                }
            }
        }
    }
    
    /**
     * Your NestedIterator object will be instantiated and called as such:
     * NestedIterator i = new NestedIterator(nestedList);
     * while (i.hasNext()) v[f()] = i.next();
     */

## 102. 二叉树的层序遍历 ##

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

示例：  
二叉树：\[3,9,20,null,null,15,7\],

![在这里插入图片描述][2021070823394039.png]

返回其层序遍历结果：

\[  
\[3\],  
\[9,20\],  
\[15,7\]  
\]

题解：这里的ArrayDeque主要的作用是队列了。把每一层的元素入队，然后依次弹出记录。

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        
        public List<List<Integer>> levelOrder(TreeNode root) {
        
            List<List<Integer>> res = new ArrayList<>();
            Queue<TreeNode> queue = new ArrayDeque<>();
            if(root != null){
        
                queue.add(root);
            }
            while(!queue.isEmpty()){
        
                List<Integer> list = new ArrayList<>();
                int n = queue.size();
                for(int i = 0; i < n; i++){
        
                    TreeNode node = queue.poll();
                    list.add(node.val);
                    if(node.left != null)
                        queue.add(node.left);
                    if(node.right != null)
                        queue.add(node.right);
                }
                res.add(list);
            }
            return res;
        }
    }

## 107. 二叉树的层序遍历 II ##

给定一个二叉树，返回其节点值自底向上的层序遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

例如：  
给定二叉树 \[3,9,20,null,null,15,7\],

![在这里插入图片描述][20210708233957920.png]

返回其自底向上的层序遍历为：

\[  
\[15,7\],  
\[9,20\],  
\[3\]  
\]

题解：把上一题的数据结构变成LinkedList<>()，用头插法实现倒序。

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        
        public List<List<Integer>> levelOrderBottom(TreeNode root) {
        
            LinkedList<List<Integer>> res = new LinkedList<>();
            Queue<TreeNode> queue = new ArrayDeque<>();
            if(root != null){
        
                queue.add(root);
            }
            while(!queue.isEmpty()){
        
                List<Integer> list = new ArrayList<>();
                int n = queue.size();
                for(int i = 0; i < n; i++){
        
                    TreeNode node = queue.poll();
                    list.add(node.val);
                    if(node.left != null)
                        queue.add(node.left);
                    if(node.right != null)
                        queue.add(node.right);
                }
                res.addFirst(list);
            }
            return res;
        }
    }

## 103. 二叉树的锯齿形层序遍历 ##

给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

例如：  
给定二叉树 \[3,9,20,null,null,15,7\],  
![在这里插入图片描述][20210708234008280.png]

返回锯齿形层序遍历如下：

\[  
\[3\],  
\[20,9\],  
\[15,7\]  
\]

题解：加一个flag判断，当其为偶数行的时候，利用Collections.reverse()，直接反转整一行即可。

class Solution {
        
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        
            List<List<Integer>> res = new ArrayList<>();
            Queue<TreeNode> queue = new ArrayDeque<>();
            if(root != null){
        
                queue.add(root);
            }
            Boolean flag = false;
            while(!queue.isEmpty()){
        
                int n = queue.size();
                List<Integer> list = new ArrayList<>();
                for(int i = 0; i < n; i++){
        
                    TreeNode node = queue.poll();
                    list.add(node.val);
                    if(node.left != null)
                        queue.add(node.left);
                    if(node.right != null)
                        queue.add(node.right);
                }
                if(flag){
        
                    Collections.reverse(list);
                }
                flag = !flag;
                res.add(list);
            }
            return res;
        }
    }

## 199. 二叉树的右视图 ##

给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例:

输入: \[1,2,3,null,5,null,4\]  
输出: \[1, 3, 4\]  
解释:  
![在这里插入图片描述][20210708234017459.png]

思路：想法很简单，就是层序遍历，然后保存最后一个节点。一开始的代码如下，

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        
        public List<Integer> rightSideView(TreeNode root) {
        
            List<Integer> res = new ArrayList<>();
            Queue<TreeNode> queue = new ArrayDeque<>();
            if(root != null){
        
                queue.add(root);
            }
            while(!queue.isEmpty()){
        
                int n = queue.size();
                ArrayDeque<Integer> queueLast = new ArrayDeque<>();
                for(int i = 0; i < n; i++){
        
                    TreeNode node = queue.poll();
                    queueLast.add(node.val);
                    if(node.left != null)
                        queue.add(node.left);
                    if(node.right != null)
                        queue.add(node.right);
                }
                res.add(queueLast.removeLast());
            }
            return res;
        }
    }

结果发现效率很低，2ms，只打败20+%的人，参考了一下大佬的代码，发现我这里有一些地方是多余的。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk1MjczNg_size_16_color_FFFFFF_t_70]我只要最后一个元素，却把很多多余的元素给添加进队列了。优化的方法就是把它去掉，然后再for里加一个判断是否为最后一轮遍历，此时的node.val就是最后一个值。变为1 ms, 在所有 Java 提交中击败了99.59% 的用户。

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        
        public List<Integer> rightSideView(TreeNode root) {
        
            List<Integer> res = new ArrayList<>();
            Queue<TreeNode> queue = new ArrayDeque<>();
            if(root != null){
        
                queue.add(root);
            }
            while(!queue.isEmpty()){
        
                int n = queue.size();
                for(int i = 0; i < n; i++){
        
                    TreeNode node = queue.poll();
                    if(node.left != null)
                        queue.add(node.left);
                    if(node.right != null)
                        queue.add(node.right);
                   	// 修改的代码
                    if(i == n - 1){
        
                        res.add(node.val);
                    }
                }
            }
            return res;
        }
    }

## 347. 前 K 个高频元素 ##

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

输入: nums = \[1,1,1,2,2,3\], k = 2  
输出: \[1,2\]

示例 2:

输入: nums = \[1\], k = 1  
输出: \[1\]

提示：

1 <= nums.length <= 105
    k 的取值范围是 [1, 数组中不相同的元素的个数]
    题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。

思路：用一个treeMap来存储数值和它的频数，建立一个优先队列，在维持里面数量为k的情况下，遍历map.keySet。最后输出结果。

import java.util.LinkedList;
    import java.util.PriorityQueue;
    import java.util.TreeMap;
    
    public class Solution {
        
        class Freq implements Comparable<Freq>{
        
            int e, freq;
    
            public Freq(int e,int freq){
        
                this.e = e;
                this.freq = freq;
            }
    
            @Override
            public int compareTo(Freq another){
        
                if(this.freq < another.freq)
                    return -1;
                else if(this.freq > another.freq)
                    return 1;
                else
                    return 0;
    
            }
    
        }
            public int[] topKFrequent(int[] nums, int k) {
        
                TreeMap<Integer,Integer> map = new TreeMap<>();
                for(int num : nums){
        
                    if(map.containsKey(num)){
        
                        map.put(num, map.get(num) + 1);
                    }else
                        map.put(num, 1);
                }
    
                PriorityQueue<Freq> pq = new PriorityQueue<>();
                for(int key : map.keySet()){
        
                    if(pq.size() < k){
        
                        pq.add(new Freq(key, map.get(key)));
                    }else if(map.get(key) > pq.peek().freq){
        
                        pq.remove();
                        pq.add(new Freq(key, map.get(key)));
                    }
                }
    
    
                int[] res = new int[k];
                int i = 0;
                while(!pq.isEmpty())
                    res[i++] = pq.remove().e;
                return res;
    
            }
    
    }

## 23. 合并K个升序链表 ##

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：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

示例 2：

输入：lists = \[\]  
输出：\[\]

示例 3：

输入：lists = \[\[\]\]  
输出：\[\]

提示：

k == lists.length
    0 <= k <= 10^4
    0 <= lists[i].length <= 500
    -10^4 <= lists[i][j] <= 10^4
    lists[i] 按 升序 排列
    lists[i].length 的总和不超过 10^4

思路：用容量为K的最小堆优先队列，把链表的头结点都放进去，然后出队当前优先队列中最小的，挂上链表，然后让出队的那个节点的下一个入队，再出队当前优先队列中最小的，直到优先队列为空。

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        
        public ListNode mergeKLists(ListNode[] lists) {
        
            if(lists.length==0)
                return null;
            // 定义一个存结果的链表
            ListNode dummy = new ListNode(0);
            ListNode cur = dummy;
            PriorityQueue<ListNode> pq = new PriorityQueue<>(new Comparator<ListNode>(){
        
                @Override
                public int compare(ListNode o1,ListNode o2){
        
                    return o1.val - o2.val;
                }
            });
    
            for(ListNode list : lists){
        
                if(list == null)
                    continue;
                pq.add(list);
            }
    
            while(!pq.isEmpty()){
        
                ListNode node = pq.poll();
                cur.next = node;
                cur = cur.next;
                if(node.next != null){
        
                    pq.add(node.next);
                }
    
            }
            return dummy.next;
        }
    }

[2021070623290088.png]: /images/20221005/5de86f4c8c5f40c1a0824176211fcf6c.png
[202107062329139.png]: /images/20221005/758fc3747ffb4596a639eca572d348ff.png
[2021070823394039.png]: /images/20221005/cabc66f085ab4dc5b1cad04fa0bb2f5c.png
[20210708233957920.png]: /images/20221005/cd5982ea8ebb4a4db69a54f14768fc22.png
[20210708234008280.png]: /images/20221005/9423f7cb707d4e2a9e369304971be649.png
[20210708234017459.png]: /images/20221005/8c7274c2b07442fc9e75fc76b57cadcf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk1MjczNg_size_16_color_FFFFFF_t_70]: /images/20221005/522367c70b824fab8821512d5413c273.png