定义 广度优先搜索，是一种按照广度优先的顺序对「问题状态空间」进行搜索的算法。 理解 对于某些特定的问题，问题状态空间可以抽象为一张图，问题状态可以类比为节点，状态之间的联系与转换关系可以类比为图中连接节点与节点的边。使用广度优先搜索算法求解这类问题，等同于在一张图上进行广度优先遍历。 回顾深度优先搜索，其算法思想为「不撞南墙不回头」，下图展示了利用深度优先搜索求解问题的搜索过程，绿色表示已经搜索

定义 记忆化搜索，是一种通过记录已经遍历过的状态的信息，从而避免对同一状态重复遍历的搜索实现方式。 理解 搜索是对一个问题不断地寻找可行方案，从初始状态开始，经过一系列状态转移，寻找目标状态或者最优状态。这是一种「通用解题方法」，但是大部分情况下搜索所需的时间复杂度都很高。 在搜索的过程中，可以记录并保存每个状态的搜索结果，在之后重复遍历这个状态时，能够直接检索并得到搜索结果。 具体应用 滑雪 滑

定义 剪枝，是一种减少搜索树规模、尽早排除搜索树中不必要分支的方法。 理解 搜索是对一个问题不断地寻找可行方案，从初始状态开始，经过一系列状态转移，寻找目标状态或者最优状态。这是一种「通用解题方法」，但是大部分情况下搜索所需的时间复杂度都很高。 一般的深度优先搜索问题都要用到回溯思想，每次不能遍历下去时，回溯到上一个点，继续遍历，整个搜索过程可以抽象成一个「搜索树」。为了降低时间复杂度，需要优化搜

定义 深度优先搜索，是一种按照深度优先的顺序对「问题状态空间」进行搜索的算法。 理解 对于某些特定的问题，问题状态空间可以抽象为一张图，问题状态可以类比为节点，状态之间的联系与转换关系可以类比为图中连接节点与节点的边。使用深度优先搜索算法求解这类问题，等同于在一张图上进行深度优先遍历。 深度优先搜索是基于递归的一种算法。递归是一种单纯的遍历方式，而深度优先搜索是一类包括遍历形式、状态记录与检索以及

定义 单调队列，即一种元素具有单调性的「双端」队列。 理解 单调队列中的元素从队首到队尾始终保持单调性（单调递增或单调递减），队首元素是所有队列元素中的一个最值（单调递增队列的队首元素是所有队列元素中的最小值，单调递减队列的队首元素是所有队列元素中的最大值）。 为了队列元素的单调性，单调队列的插入操作涉及两个步骤： 将一个元素插入单调栈队列之前，需要「在保证将该元素插入到队尾后整个队列满足单调

队列 定义 队列，是一种「先进先出」的线性数据结构。 理解 一般情况下，元素从一端进入队列，从另一端离开队列。元素进入的一端称为队尾，元素离开的一端称为队首。 添加元素时，只能将其插入到队尾（即入队操作）；删除元素时，只能将队首元素从队列中取出（即出队操作）。 代码模板 涉及到队列的操作，可以方便地利用标准模板库 STL 中的 queue 实现。 123456789101112queue<i

定义 单调栈，即一种栈内元素具有单调性的栈。 理解 单调栈内的元素从栈顶到栈底始终保持单调性（单调递增或单调递减），栈顶元素是所有栈内元素的一个最值（单调递增栈的栈顶元素是所有栈内元素的最小值，单调递减栈的栈顶元素是所有栈内元素的最大值）。 为了栈内元素的单调性，单调栈的插入操作涉及两个步骤： 将一个元素插入单调栈之前，需要「在保证将该元素插入到栈顶后整个栈满足单调性的前提下」弹出最少的元素。

定义 栈，是一种「后进先出」的线性数据结构。 理解 栈，只有一端能够进出元素，一般称这一端为栈顶，另一端为栈底。 添加或者删除栈中元素时，只能将其插入到栈顶（即入栈操作），或者把栈顶元素从栈中取出（即出栈操作）。 代码模板 涉及到栈的操作，可以方便地利用标准模板库 STL 中的 stack 实现。 1234567891011stack<int> stk; // 定义一个栈int num

定义 排序算法，是一种将一组特定的数据按某种顺序进行排列的算法。 理解 排序，就是将输入数据按照一定的顺序重新排列，得到有序的输出数据。 最常用的排序方式是数值顺序以及字典顺序。 最终的输出数据，有以下两个特点： 是已经按照特定的顺序排列好的有序序列。 是输入序列的一种排列或重组。 常用排序算法 理解排序的概念是很容易的，但实现排序的方式多种多样。 常用的排序算法包括：选择排序、冒泡排序、插入

定义 贪心算法，又称贪婪算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。 理解 贪心，就是用计算机来模拟一个「贪婪」的人做出决策的过程。 在解决问题的过程中，每一步行动总是在当前已有条件下，按某种指标选取最优的操作，并不考虑以后可能造成的影响。 可想而知，在这种策略下，并不是所有的情况贪心法都能获得最优解，所以一般使用贪心法的时候，都要