总言
主要内容：编程题举例，熟悉理解宽搜类题型，队列、堆此类STL容器使用。
文章目录
1、 宽搜
搜索类算法有：深搜、宽搜。深搜我们在之前的博文中举例过很多例题。（递归&&二叉树深搜、回溯和剪枝（暴搜/深搜））
这里，我们主要举例几道题目熟悉宽搜，由于宽搜是借助队列完成，因此此处例题也是对队列相关数据结构和容器的熟悉使用。其应用延伸会在floodfill和记忆化搜索中举例。
相关复习博文：数据结构：栈&&队列、STL：stack&&queue
2、N 叉树的层序遍历（medium）
题源：链接。
2.1、题解
1）、思路分析
说明： 我们曾写过二叉树的层序遍历（相关连接），这里原理相同，BFS需要借助栈来完成，无非是把二叉树改为了多叉树。
注意细节： 在使用BFS遍历时，我们只是一股脑地将结果以层序遍历的方式打印出来。但这里的返回值为vector<vector<int>>，要求我们分层处理。
如何控制BFS，每次只获取每层的结果？ 我们可以使用一个变量levelsize来统计一层的结点数。那么每次出队列时，只需出这levelsize个结点即可。（PS：这里具体写法形式不固定，只要按照解题思路写出来即可，细节控制看自己。）
2）、题解
这种写法是在while总循环前就先统计一层的结点数量，每当出完 levelsize 个结点，就代表完成一层的遍历。此时队列剩余的元素即下一层的结点数目。
class Solution {
public:
vector<vector<int>> levelOrder(Node* root) {
vector<vector<int>> ret;// 用于返回最终结果(所有层)
vector<int> level;// 用于统计每一层
if(root == nullptr) return ret;// 题目结点存在空的情况
std::queue<Node*> q;// 队列：用于层序遍历
if(root)
q.push(root);
int levelsize = q.size();// 用于统计每一层的节点个数
while(!q.empty())
{
Node* front = q.front();// 取队头元素
q.pop();// 删除队头元素
for(auto node : front->children)// 让当前结点的孩子⼊队
{
if(node != nullptr)
q.push(node);
}
level.push_back(front->val);//将当前取出的结点放入当前层统计中
if(--levelsize <= 0)// 每放一次，就减一次当前层的结点数目，如果减到零，说明当前层已经出完，合计一次。
{
ret.push_back(level);
level.clear();// 清空
levelsize = q.size();// 此时队列中存在的元素数目，就是下一层结点的总个数
}
}
return ret;
}
};
这种写法是在每一层遍历开始前，先记录队列中的结点数量 levelsize（也就是这一层的结点数量），然后通过 for 循环，一次只处理 levelsize 个结点（也就是一次只出一层的结点数量）。
class Solution {
public:
vector<vector<int>> levelOrder(Node* root) {
vector<vector<int>> ret;// 用于返回最终结果(所有层)
if(root == nullptr) return ret;// 题目结点存在空的情况
std::queue<Node*> q;// 队列：用于层序遍历
if(root)
q.push(root);
while(q.size())// 队列不为空时
{
int levelsize = q.size();// 统计当前队列中的元素个数（即当前层的总个数）
vector<int> level;// 用于统计每一层
for(int i = 0; i < levelsize; ++i)// 只需要出队levelsize次，即可出完当前层的所有元素，此时队列剩余的元素即下一层的结点数目
{
Node* front = q.front();// 取数
q.pop();//删数
level.push_back(front->val);
for(auto node : front->children)
{
q.push(node);
}
}
ret.push_back(level);// 将一层数据计入最终返回结果中
}
return ret;
}
};
3、二叉树的锯齿形层序遍历（medium）
题源：链接。
3.1、题解
1）、思路分析
整体BFS思路不变，只是在适当的层需要进行逆序。因此，可额外增加一个标记位，让偶数层获取到的集合元素逆序即可。
2）、题解
标记位使用bool类型变量的方法：
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> ret;// 用于记录最终所有层的结果
if(root == nullptr) return ret;
std::queue<TreeNode*> q;// 用于进行层序遍历的队列
bool flag = false;// 标记位：主要用来进行锯齿操作（false时：从左往右；true时，从右往左）
q.push(root);
while(!q.empty())// 队列不为空
{
int levelsize = q.size();// 统计当前层有多少结点
vector<int> level;// 用于记录一层的遍历结果
for(int i = 0; i < levelsize; ++i)// 根据统计结果，将当前层的结点出队
{
TreeNode* front = q.front();// 取队头
q.pop();// 出队
level.push_back(front->val);// 记录
if(front->left) q.push(front->left);// 左孩子不为空，入队
if(front->right) q.push(front->right);// 右孩子不为空，入队
}
if(flag)// 若flag为true，则逆序一次（相当于从右到左）
reverse(level.begin(),level.end());
ret.push_back(level);//将当前层计入最终统计结果中
flag = !flag;// 修改标记位，以便下一层操作
}
return ret;
}
};
标记位使用int变量记录层数的方法：
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> ret;// 用于记录最终所有层的结果
if(root == nullptr) return ret;
std::queue<TreeNode*> q;// 用于进行层序遍历的队列
int curlevel = 1;// 标记位：主要用来进行锯齿操作（这里记录的是层数）
q.push(root);
while(!q.empty())// 队列不为空
{
int levelsize = q.size();// 统计当前层有多少结点
vector<int> level;// 用于记录一层的遍历结果
for(int i = 0; i < levelsize; ++i)// 根据统计结果，将当前层的结点出队
{
TreeNode* front = q.front();// 取队头
q.pop();// 出队
level.push_back(front->val);// 记录
if(front->left) q.push(front->left);// 左孩子不为空，入队
if(front->right) q.push(front->right);// 右孩子不为空，入队
}
if(curlevel % 2 == 0)// 能被2除尽，说明是偶数层，需要从右往左
reverse(level.begin(),level.end());
ret.push_back(level);//将当前层计入最终统计结果中
++curlevel;// 进入下一层
}
return ret;
}
};
4、二叉树的最大宽度（medium）
题源：链接。
4.1、题解
1）、思路分析
思路一： 层层遍历，统计队列宽度（会超过内存限制）。
利用层序遍历，把当前层的结点全部存在队列里面，利用队列的长度来计算每一层的宽度，统计出最大的宽度。需要注意，这里空节点也是需要计算在在队列内的。
超时说明： 树中节点的数目范围是 [1, 3000]，极端情况下，设只有最左边和最右边的长链，此时我们需要存几亿个空节点，会超过最⼤内存限制。
思路二： 利用二叉树的顺序存储。通过根节点的下标，计算左右孩子的下标。
2）、题解
class Solution {
public:
int widthOfBinaryTree(TreeNode* root) {
if(root == nullptr) return 0;
vector<pair<TreeNode*,unsigned int>> q;// 用数组模拟队列
unsigned int maxwidth = 0;// 用于记录最宽的长度
q.push_back({root,1});// 入队：这里将根结点编号设置为1
while(!q.empty())// 不为空时
{
// 取当前层的首元素和尾元素，获取宽度差
auto& [x1,y1] = q.front();
auto& [x2,y2] = q.back();
maxwidth = max(maxwidth, y2 - y1 + 1);// 这里y1、y2是对应结点的编号。
// 入队下一层
vector<pair<TreeNode*,unsigned int>> next;// 这里我们选择重新建立一个队列进行替换，如此可以省去出队时vector的头删（需要挪动数据）
for(auto& [x,y] : q)
{
if(x->left) next.push_back({x->left, y*2});// 若左结点存在，将左结点入队
if(x->right) next.push_back({x->right,y*2+1});// 若右结点存在，将右结点入队
}
q = next;// 替换
}
return maxwidth;
}
};
5、在每个树行中找最大值（medium）
题源：链接。
5.1、题解
1）、思路分析
说明： 可以在BFS层序遍历过程中，统计出每⼀层结点的最大值。
2）、题解
class Solution {
public:
vector<int> largestValues(TreeNode* root) {
vector<int> ret;
if(root == nullptr) return ret;
std::queue<TreeNode*> q;// 用于层序遍历的队列
q.push(root);// 将根结点入队
while(!q.empty())
{
int maxinlevel = INT_MIN;// 用于记录当前层的最大值
int sizelevel = q.size();// 当前层的元素个数
for(int i = 0; i < sizelevel; ++i)
{
TreeNode* front = q.front();
q.pop();
maxinlevel = max(maxinlevel,front->val);
if(front->left) q.push(front->left);
if(front->right) q.push(front->right);
}
ret.push_back(maxinlevel);//一层遍历完，将当前层的最大值存入最终结果汇总
}
return ret;
}
};
6、优先级队列
前情回顾（方便复习）：
数组堆：相关博文链接
priority_queue容器使用：相关博文链接
7、最后一块石头的重量（easy）
题源：链接。
7.1、题解
1）、思路分析
说明：此题其实就是一个模拟的过程。可建立一个大堆，每次从石堆中拿出最大及次大的元素，将二者粉碎（做相关运算）；如果运算结果还有剩余，就将剩余的结果存入原始的堆中。一直重复上述操作，直到堆中只剩下⼀个元素，或没有元素。
2）、题解
class Solution {
public:
int lastStoneWeight(vector<int>& stones) {
priority_queue<int> heap;//创建一个大堆，将数据放入堆中
for(auto e: stones)
heap.push(e);
while( heap.size() > 1)// 堆中存在两个及其以上的元素时，才取石头
{
int y = heap.top();heap.pop();// 大堆，取当前最大值。
int x = heap.top();heap.pop();// 取次大值。
int tmp = y - x;// 进行粉碎
if(tmp) heap.push(tmp);// 若 x != y,将结果存入堆中
}
if(heap.size()) return heap.top();//若只剩下一块石头，返回此石头的重量。
else return 0;//如果没有石头剩下，就返回 0。
}
};
8、数据流中的第 K 大元素（easy）
题源：链接。
8.1、题解
1）、思路分析
看到此题时，要想到它实际是TOP-K问题：从一个包含大量数据项的集合中找到前K个最重要（最大/最小）的元素。
在学习数据结构堆时，我们讲过可以使用堆排序解决（相关链接）。时间复杂度为 O ( n l o g k ) O(nlogk) O(nlogk)。
在先前的并归专题我们也使用过快速选择排序解决（相关链接）。时间复杂度为 O ( n ) O(n) O(n)。
2）、题解
这里我们主要以堆排解决该问题。要注意理解，排升序要用大根堆还是小根堆？为什么？（相关问题见链接部分的博文）
class KthLargest {
public:
KthLargest(int k, vector<int>& nums)
:_k(k)
{
int n = nums.size();
// 建立一个小堆，放入k个元素。
for(auto x : nums)
{
heap.push(x);
if(heap.size() > _k) heap.pop();
}
}
int add(int val) {
heap.push(val);
if(heap.size() > _k) heap.pop();
return heap.top();
}
int _k;
priority_queue<int,vector<int>,greater<int>> heap;
// priority_queue默认大堆，用的是less；这里我们要创建小队，故类模板需要定义。
};
/**
* Your KthLargest object will be instantiated and called as such:
* KthLargest* obj = new KthLargest(k, nums);
* int param_1 = obj->add(val);
*/
9、前 K 个高频单词 （medium）
题源：链接。
9.1、题解
1）、思路分析
此题实际也是一个top-K 问题。要知道每⼀个单词出现的频次，因此可以先使用哈希表，统计出每一个单词出现的频次，然后在哈希表中，选出前 k 大的单词。（原数组中存在重复的单词，哈希表处理后无重复单词）
统计完毕后，需要进行排序。 方法多种，这里主要讲解堆排(优先级队列的使用)：排序需要满足两重条件。第一序列看单词频率，频率大的优先（基于频次比较的小根堆）；第二序列看字典顺序，字母小的排在前面（基于字典序比较的大根堆）。
定义好用于比较的容器后，依次将哈希表中的字符串插入到堆中，维持堆中的元素不超过 k 个；遍历完整个哈希表后，堆中的剩余元素就是前 k 大的元素。此时，需要将堆中元素提取返回。（这里取堆顶元素得到的是逆序，可以先将所有元素放入数组中来一次逆置，也可以直接倒着存入元素。）
其它写法：map、set系列容器运用。
2）、题解
class comple {
public:
bool operator()(const pair<string, int>& x, const pair<string, int>& y)
{
if(x.second == y.second)
return x.first < y.frist;// 单词频率相同时，按照字典顺序比较(大根堆)
return x.second > y.second;// 按照单词出现频率比较(这里建立的是小根堆)
}
}
class Solution {
public:
vector<string> topKFrequent(vector<string>& words, int k) {
unordered_map<string, int>hash; // 定义一个哈希，用于统计单词及其出现频率
for (auto& str : words) // 统计频率
hash[str]++;
// 使用堆排
priority_queue<pair<string, int>, vector<pair<string, int>>, comple> heap;
for(auto& pai : hash)
{
heap.push(pai);
if(heap.size() > 0) heap.pop();
}
// 提取k个元素
vector<string> ret(k);
for(int i = k-1; i >= 0; --k)// 从后往前提取堆顶元素放入，可省去逆置
{
ret[i] = heap.top();
heap.pop();
}
return ret;
}
};
10、数据流的中位数（hard）
题源：链接。
10.1、题解
1）、思路分析
思路一（超时）： 使用vector容器存放序列，在每次查找中位数前进行快排，通过下标即可快速找到中位数。时间复杂度： a d d ( n l o g n ) add(nlogn) add(nlogn)、 f i n d ( 1 ) find(1) find(1)
思路二（超时）： 可以使用插入排序。时间复杂度： a d d ( n ) add(n) add(n)、 f i n d ( 1 ) find(1) find(1)
思路三：利用大小堆维护数据流中的中位数。
我们可以将整个数组按照大小平均分成两个序列，左序列和右序列（如果不能平分，那就让左侧较小的序列的元素多一个）。
对左序列的元素，建立大根堆；对右序列的元素，建立小根堆。这样就能在 O ( 1 ) O(1) O(1) 的时间内拿到中间的一个数或者两个数，进而求得平均数。
2）、题解
class MedianFinder {
// 使用两个堆来维护数据流：[0,mid]建立大根堆，即包含中位数在内的左侧m个元素，[mid+1, n]建立小根堆，即中位数之后的n个元素。
// 根据上述，由于数据存在偶数、奇数情况。这里我们默认将中位数放在大根堆中(即左区间中)，则有m >= n (只会比n多一个元素)
priority_queue<int> max_left;// 左区间：大根堆
priority_queue<int, vector<int>,greater<int>> min_right;// 右区间：小根堆
public:
MedianFinder() {
}
void addNum(int num) {
int m = max_left.size(), n = min_right.size();// 获取当前两个堆中元素数目
// 合法的情况：m == n、 m = n + 1。要保证放入元素num后，仍旧满足合法条件。
if(m == n)// 放置元素num前，大根堆和小根堆元素相同
{
if(m == 0 || num <= max_left.top()) // 待加入元素需要放在左侧大根堆中，放入后 m = n + 1
{
max_left.push(num);
}
else{ // 待加入元素需要放在右侧小根堆中，放入后 m + 1 = n，因此需要挪动右侧堆顶元素入左侧（挪动后 m == n）
min_right.push(num);
max_left.push(min_right.top());
min_right.pop();// 这里删除顺序不能乱。有可能放入的num恰好是右边小根堆的堆顶元素。
}
}
else if(m == n + 1)// m > n
{
if(num <= max_left.top())// 待加入元素需要放在左侧大根堆中，放入后 m = n +2 ，因此则需要挪动左侧堆顶元素入右侧（挪动后：m == n）
{
max_left.push(num);// 将num元素放入左侧大根堆中：m = n + 2;
min_right.push(max_left.top());// 将左侧大根堆中堆顶元素取出放入右侧小根堆中：m = n
max_left.pop();
}
else// num > left
{
min_right.push(num);// 放入后，m = n
}
}
}
double findMedian() {
int m = max_left.size(), n = min_right.size();// 获取当前两个堆中元素数目
if(m == n)
{
return (max_left.top() + min_right.top()) / 2.0; // 注意整数除法和小数除法
}
else return max_left.top();
}
};
Fin、共勉。
