题目主要信息： 寻找数据的中位数 数据量在不断输入增长 举一反三： 学习完本题的思路你可以解决如下题目： BM46. 最小的k个数 方法一：插入排序法（推荐使用） 知识点：插入排序 插入排序是排序中的一种方式，一旦一个无序数组开始排序，它前面部分就是已经排好的有序数组（一开始长度为0），而其后半部分则是需要排序的无序数组，插入排序的做法就是遍历后续需要排序的无序部分，对于每个元素，插入到前半部分有序数组中属于它的位置——即最后一个小于它的元素后。 思路： 传统的寻找中位数的方法便是排序之后，取中间值或者中间两位的平均即可。但是这道题因为数组在不断增长，每增长一位便需要排一次，很浪费时间，于...

题目主要信息： 利用快速排序的思想寻找数组中的第k大元素 有重复数字，不用去重，也不用管稳定性与否 举一反三： 学习完本题的思路你可以解决快速排序或者分治类的问题： BM5. 合并k个有序链表 BM20. 数组中的逆序对 方法：快排+二分查找（推荐使用） 知识点：分治 分治即“分而治之”，“分”指的是将一个大而复杂的问题划分成多个性质相同但是规模更小的子问题，子问题继续按照这样划分，直到问题可以被轻易解决；“治”指的是将子问题单独进行处理。经过分治后的子问题，需要将解进行合并才能得到原问题的解，因此整个分治过程经常用递归来实现。 思路： 本题需要使用快速排序的思想，快速排序：每次移动，可以...

题目主要信息： 对于一个给定无序数组，返回最小的k个元素，顺序任意 k和数组有特殊情况需要单独讨论 举一反三： 学习完本题的思路你可以解决如下题目： BM48. 数据流中的中位数 BM5. 合并k个有序链表 方法一：堆排序（推荐使用） 知识点：优先队列 优先队列即PriorityQueue，是一种内置的机遇堆排序的容器，分为大顶堆与小顶堆，大顶堆的堆顶为最大元素，其余更小的元素在堆下方，小顶堆与其刚好相反。且因为容器内部的次序基于堆排序，因此每次插入元素时间复杂度都是O(log2n)O(log_2n)O(log2​n)，而每次取出堆顶元素都是直接取出。 思路： 要找到最小的k个元素，只需要...

题目主要信息： 要寻找每个滑动窗口的最大值，每次只滑一位 size等于0或者大于数组长度，都返回空值 举一反三： 学习完本题的思路你可以解决双向队列或者滑动窗口的题目： BM92.最长无重复子数组 方法一：双向队列（推荐使用） 知识点：双向队列 如果说队列是一种只允许从尾部进入，从头部出来的线性数据结构，那双向队列就是一种特殊的队列了，双向队列两边，即头部和尾部都可以进行插入元素和删除元素的操作，但是也只能插入到最尾部或者最头部，每次也只能取出头部元素或者尾部元素后才能取出里面的元素。 思路： 我们都知道，若是一个数字A进入窗口后，若是比窗口内其他数字都大，那么这个数字之前的数字都没用了，...

题目主要信息: 给定一个只包含大中小左右括号的字符串，判断其中括号是否合法 大中小括号的数学顺序与合法无关，只需要每种左括号在右边有相应匹配的右括号即可，不可交叉匹配，应该是括号嵌套 举一反三： 学习完本题的思路你可以解决如下题目： BM49. 表达式求值 方法：栈（推荐使用） 知识点：栈 栈是一种仅支持在表尾进行插入和删除操作的线性表，这一端被称为栈顶，另一端被称为栈底。元素入栈指的是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；元素出栈指的是从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。 思路： 括号的匹配规则应该符合先进后出原理：最外层的...

题目主要信息： 实现栈的push、pop、top、min函数 访问每个函数的时间复杂度为O(1)O(1)O(1) 举一反三： 学习完本题的思路你可以解决如下题目： BM42.用两个栈实现队列 方法：双栈法（推荐使用） 知识点：栈 栈是一种仅支持在表尾进行插入和删除操作的线性表，这一端被称为栈顶，另一端被称为栈底。元素入栈指的是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；元素出栈指的是从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。 思路： 我们都知道栈结构的push、pop、top操作都是O(1)O(1)O(1)，但是min函数做不到，于是想到...

题目主要信息: 队列：元素不可直接下标访问，先进先出 栈：元素不可直接访问，先进后出 使用两个栈模拟在队列中插入n个元素和弹出n个元素，顺序不定，但是保证操作都是合法的 举一反三： 学习完本题的思路你可以解决如下题目： BM43. 包含min函数的栈 方法：双栈法（推荐使用） 知识点1：栈 栈是一种仅支持在表尾进行插入和删除操作的线性表，这一端被称为栈顶，另一端被称为栈底。元素入栈指的是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；元素出栈指的是从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。 知识点2：队列 队列是一种仅支持在表尾进行插入操作、...

题目的主要信息： 利用二叉树中序遍历结果及前序遍历结果构建一棵二叉树 打印二叉树的右视图，即二叉树每层最右边的节点元素 节点值互不相同 举一反三： 学习完本题的思路你可以解决如下题目： BM40. 重建二叉树 BM38. 在二叉树中找到两个节点的最近公共祖先 BM29. 二叉树中和为某一值的路径（一） BM26. 求二叉树的层次遍历 方法一：递归建树+深度优先搜索（推荐使用） 知识点1：二叉树递归 递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分...

题目的主要信息： 根据二叉树的前序遍历序列和中序遍历序列，重建该二叉树，并返回根节点 两个遍历都没有重复的元素 举一反三： 学习完本题的思路你可以解决如下题目： BM41. 输出二叉树的右视图 方法一：递归（推荐使用） 知识点：二叉树递归 递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键。 而二叉树的递归，则是将某个节点的左子树、右子树看成一颗完整的树，那么对于子树的访问或者操作就是对于原树的访问或者操作的子...

题目主要信息： 序列化二叉树即找一种顺序存储二叉树的节点，并以相同的方式能够读取序列重新构建。 换种说法，就是遍历二叉树，记录每个节点，再以同样的方式遍历就可以还原二叉树。 遍历的方法有四种：前序遍历、中序遍历、后序遍历、层次遍历，理论上只要以相同的方式序列化或者反序列化，都可以解题。 举一反三： 学习完本题的思路你可以解决如下题目： BM28. 二叉树的最大深度 BM29. 二叉树中和为某一值的路径（一） BM31. 对称的二叉树 BM32. 合并二叉树 BM33. 二叉树的镜像 BM36. 判断是不是平衡二叉树 BM41. 输出二叉树的右视图 方法：前序遍历（推荐使用） 知识点：二叉树...

题目的主要信息： 给定一棵二叉树以及这棵树上的两个节点对应的val值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点 二叉树非空，且每个节点值均不同 举一反三： 学习完本题的思路你可以解决如下题目： BM29. 二叉树中和为某一值的路径（一） BM37. 二叉搜索树的最近公共祖先 方法一：路径比较法(推荐使用) 知识点：深度优先搜索（dfs） 深度优先搜索一般用于树或者图的遍历，其他有分支的（如二维矩阵）也适用。它的原理是从初始点开始，一直沿着同一个分支遍历，直到该分支结束，然后回溯到上一级继续沿着一个分支走到底，如此往复，直到所有的节点都有被访问到。 思路： 既然要找到二叉树...

题目的主要信息： 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先： 对于该题的最近的公共祖先定义：对于有根树T的两个节点p、q，最近公共祖先LCA(T,p,q)表示一个节点x，满足x是p和q的祖先且x的深度尽可能大 一个节点也可以是它自己的祖先 二叉搜索树是若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值 所有节点的值都是唯一的，可以通过节点值直接比较 p、q 为不同节点且均存在于给定的二叉搜索树中 举一反三： 学习完本题的思路你可以解决如下题目： BM30. 二叉搜索树与双向链表 BM38. 在二叉树中...

题目主要信息： 判断给出的二叉树是否是平衡二叉树 需要判断任意一节点两边子树深度相差是否绝对值大于1，同时它的子树也符合平衡二叉树的规则 举一反三： 学习完本题的思路你可以解决如下题目： BM28. 二叉树的最大深度 BM29. 二叉树中和为某一值的路径（一） BM31. 对称的二叉树 BM32. 合并二叉树 BM33. 二叉树的镜像 BM39. 序列化二叉树 BM41. 输出二叉树的右视图 方法一：自顶向下（推荐使用） 知识点：二叉树递归 递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递...

题目主要信息： 判断给定二叉树是否为完全二叉树 首先我们需要知道什么是完全二叉树：叶子节点只能出现在最下层和次下层，且最下层的叶子节点集中在树的左部。 需要注意的是，满二叉树肯定是完全二叉树，而完全二叉树不一定是满二叉树。 举一反三： 学习完本题的思路你可以解决如下题目： BM26. 求二叉树的层次遍历 BM27. 按之字形顺序打印二叉树 方法：层次遍历（推荐使用） 知识点：队列 队列是一种仅支持在表尾进行插入操作、在表头进行删除操作的线性表，插入端称为队尾，删除端称为队首，因整体类似排队的队伍而得名。它满足先进先出的性质，元素入队即将新元素加在队列的尾，元素出队即将队首元素取出，它后一个...