Appearance
22 数据结构模板：如何让解题变成搭积木？
在这个模块，我把常见的"套路"题，帮你总结成手写代码时应该准备的各种代码模板。还会把自己压箱底的独家代码模板分享给你，利用它，我多次在 10 分钟以内拿下了算法面试。
今天我先带你把数据结构部分做一个归纳和整理，方便你考前复习和平日积累。可以想象一下，如果在准备面试期间，你已经刷了很多题，那么在临近面试时还可以做些什么呢？
把所有写过的代码再看一遍？
把前面 20 讲的内容从头到尾再复习一遍？
还是继续刷题？
在我个人看来，以上这些方法都不可取，此时最行之有效的方法是将学过的知识尽可能地压缩、再压缩，最后形成模板。整理模板，有以下几个好处。
组合：其实大部分面试题都是一些算法模块的组合，并不需要我们真正去发明一个算法。
速度：面试写题时速度更快，一些常用的功能性代码可以直接粘贴过去，不用在打字和调试上浪费时间。
重点：可以在有限的时间里重点关注整理好的代码模板，告别"大海捞针"式的复习。
其实面试中考察的那些高频知识点，就像一块块"积木"，而面试求解过程就像"搭积木的游戏"。高效利用代码模版的技巧，能够帮助你在面试时写出更高效和 0 Bug 的代码。
说明：一些扩展知识点，我会通过练习题的形式给出来。
栈
在《01 | 栈：从简单栈到单调栈，解决经典栈问题》中，我们将栈的知识总结在了下面这张知识导图中。
简单栈的性质
后面我们又在《20 | 5 种解法，如何利用常量空间求解最长有效括号长度？》的"特点 4"中，介绍了另一个栈的重点性质------括号匹配时栈的性质。我们可以用如下代码模板展示这个性质：
java
int longestValidParentheses(String s) {
final int N = s == null ? 0 : s.length();
if (N <= 1) {
return 0;
}
Stack<Integer> st = new Stack<>();
// 最长的有效长度
int ans = 0;
int start = 0;
for (int i = 0; i < N; i++) {
final char c = s.charAt(i);
if (c == ')') {
// 如果从[start, i]这个区间里面
// 右括号已经可以匹配掉所有的左括号了
if (st.isEmpty()) {
// 问题2:更新新字符串的开头
start = i + 1;
} else {
st.pop();
// 注意问题1，3在这里统一处理
final int base =
st.isEmpty() ? start : st.peek() + 1;
ans = Math.max(ans, i - base + 1);
}
} else { /* 如果字符是左括号 */
st.push(i);
}
} // end for
return ans;
}
}栈的模拟主要是使用其他数据结构来模拟栈的 push/pop 操作，主要涉及 3 个经典的题目，即下面的练习题 1、练习题 2 以及练习题 3。
练习题 1：请使用两个队列实现栈的 push/pop/empty/size 四种操作。
练习题 2：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
练习题 3：定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
单调栈
单调栈中经常还会用来解决这类题目：数组中元素右边第一个比元素自身小的元素的位置。
java
int[] findRightSmall(int[] A) {
// 结果数组
int[] ans = new int[A.length];
// 注意，栈中的元素记录的是下标
Stack<Integer> t = new Stack();
for (int i = 0; i < A.length; i++) {
final int x = A[i];
// 每个元素都向左遍历栈中的元素完成消除动作
while (!t.empty() && A[t.peek()] > x) {
// 消除的时候，记录一下被谁消除了
ans[t.peek()] = i;
// 消除时候，值更大的需要从栈中消失
t.pop();
}
// 剩下的入栈
t.push(i);
}
// 栈中剩下的元素，由于没有人能消除他们，因此，只能将结果设置为-1。
while (!t.empty()) {
ans[t.peek()] = -1;
t.pop();
}
return ans;
}还有 3 类问题与上面这道题目类似，一般而言，深入理解其中一个模板即可。
数组中元素右边第一个比我大的元素的位置
数组中元素左边离我最近且比我小的元素的位置
数组中元素左边离我最近且比我大的元素的位置
单调栈的性质
我们将单调栈的性质总结为以下两点，更详细的介绍你可以回到《16 | 如何利用 DP 与单调队列寻找最大矩形？》进行复习。
当单调递增栈中存放数组下标 i, j, k 时，其中 (i, k] 中的元素 > A[j]；
当单调递增栈中存放数组下标 i, j，并且当 A[k] 入栈，会把栈顶元素 A[j]"削"出栈时，其中 (j, k) 元素 > A[j]。
我们曾经用到单调栈性质的模板代码求解最大矩形，如下所示：
java
int largestRectangleArea(int[] A) {
final int N = A == null ? 0 : A.length;
// 虽然可以用Stack<Integer>，但是这里为了更快地操作，我们用
// 数组模拟栈来运行，因为我们知道最多存放的内容实际上就是N个
int top = 0;
// s[top-1]表示栈顶元素
int[] s = new int[N];
int ans = 0;
// 注意，这里我们取到了i == N
// 按理说，不应该取到i == N的。但是这时候主要是为了处理这种数组
// A = [1, 2, 3]
// 没有任何元素会出栈。
// 那么最后我们用一个0元素，把所有的元素都削出栈。
// 这样代码就可以统一处理掉。
for (int i = 0; i <= N; i++) {
// 注意：当i == N的时候，x = -1;
// 比数组中的元素都要小。
final int x = i == N ? -1 : A[i];
while (top > 0 && A[s[top - 1]] > x) {
// 计算以A[s[top]]的元素的高度的矩形。
final int height = A[s[--top]];
// i元素要将index = s[top-1]的元素出栈。
// 那么根据性质2/3：
// 此时A[s[top-1] .... i) 这个区间里面的元素都是
// 大于A[s[top-1]]的
final int rightPos = i;
// 这里需要使用性质1.
// 注意：当栈中一个元素都没有的时候，要取-1
final int leftPos = top > 0 ? s[top - 1] : -1;
final int width = rightPos - leftPos - 1;
final int area = height * width;
ans = Math.max(ans, area);
}
s[top++] = i;
}
return ans;
}队列
关于队列的知识点，我们同样总结在了一张思维导图中，如下所示：
队列的数据结构知识点一般有 5 个：
FIFO 队列
循环队列（模板）
单调队列（模板）
堆（模板）
优先级队列
不过一般而言，需要重点掌握的数据结构的模板只有 3 个，即循环队列、单调队列以及堆。
循环队列
首先我们看一下使用数组来实现循环队列的写法，代码如下：
java
class MyCircularQueue {
// 已经使用的元素个数
private int used = 0;
// 第一个元素所在位置
private int front = 0;
// rear是enQueue可在存放的位置
// 注意开闭原则
// [front, rear)
private int rear = 0;
// 循环队列最多可以存放的元素个数
private int capacity = 0;
// 循环队列的存储空间
private int[] a = null;
public MyCircularQueue(int k) {
// 初始化循环队列
capacity = k;
a = new int[capacity];
}
public boolean enQueue(int value) {
// 如果已经放满了
if (isFull()) {
return false;
}
// 如果没有放满，那么a[rear]用来存放新进来的元素
a[rear] = value;
// rear注意取模
rear = (rear + 1) % capacity;
// 已经使用的空间
used++;
// 存放成功!
return true;
}
public boolean deQueue() {
// 如果是一个空队列，当然不能出队
if (isEmpty()) {
return false;
}
// 第一个元素取出
int ret = a[front];
// 注意取模
front = (front + 1) % capacity;
// 已经存放的元素减减
used--;
// 取出元素成功
return true;
}
public int Front() {
// 如果为空，不能取出队首元素
if (isEmpty()) {
return -1;
}
// 取出队首元素
return a[front];
}
public int Rear() {
// 如果为空，不能取出队尾元素
if (isEmpty()) {
return -1;
}
// 注意：这里不能使用rear - 1
// 需要取模
int tail = (rear - 1 + capacity) % capacity;
return a[tail];
}
// 队列是否为空
public boolean isEmpty() {
return used == 0;
}
// 队列是否满了
public boolean isFull() {
return used == capacity;
}
}单调队列
接下来，我们看一下单调队列的实现代码。单调队列有两种，即递增队列和递减队列。由于这两种队列的代码模版非常类似，因此只需要记住其中一个就可以了，递减队列代码如下：
java
class Solution {
// 单调队列使用双端队列来实现
private ArrayDeque<Integer> Q = new ArrayDeque<Integer>();
// 入队的时候，last方向入队，但是入队的时候
// 需要保证整个队列的数值是单调的
// (在这个题里面我们需要是递减的)
// 并且需要注意，这里是Q.getLast() < val
// 如果写成Q.getLast() <= val就变成了严格单调递增
private void push(int val) {
while (!Q.isEmpty() && Q.getLast() < val) {
Q.removeLast();
}
// 将元素入队
Q.addLast(val);
}
// 出队的时候，要相等的时候才会出队
private void pop(int val) {
if (!Q.isEmpty() && Q.getFirst() == val) {
Q.removeFirst();
}
}此外，单调队列还可以使用"< 元素值，下标 > 同时入队和出队"的方法来实现。这两种实现本质上没有太大的区别。你可以根据你对单调队列理解程度选择一种作为做通用模板。
堆
由于堆往往用来实现优先级队列，因此，这里我也整理好了堆的实现的代码：
java
class Heap {
private int[] a = null;
private int n = 0;
// 下沉
public void sink(int i) {
int j = 0;
int t = a[i];
// 找到i结点的左子结点
while ((j = (i << 1) + 1) < n) {
// j < n - 1判断是否有右子结点
// 如果有，并且右子结点更大，那么
// j指向右子结点
if (j < n - 1 && a[j] < a[j + 1]) {
j++;
}
// 如果子结点比t大
// 那么t的位置还需要往后排
if (a[j] > t) {
a[i] = a[j];
i = j;
} else {
// 找到了t的位置
// 此时t是大于所有的子结点的
break;
}
}
// 将t放在找到的位置那里
a[i] = t;
}
// 上浮
public void swim(int i) {
int t = a[i];
int par = 0;
// 如果还存在父结点
while (i > 0 && (par = (i - 1) >> 1) != i) {
// 如果父结点比t值小
if (a[par] < t) {
a[i] = a[par];
i = par;
} else {
break;
}
}
a[i] = t;
}
public void push(int v) {
// push是先把元素追加到数组尾巴上，然后再执行上浮操作
a[n++] = v;
swim(n - 1);
}
public int pop() {
int ret = a[0];
a[0] = a[--n];
sink(0);
return ret;
}
public int size() {
return n;
}
}链表
要想解决链表题，我们首先需要掌几种最基本的操作，如下图所示：
不知道你是否还记得，我在《04 | 链表：如何利用"假头、新链表、双指针"解决链表题？（上）》中，将这几种操作整理成了一个代码模板。其核心思想就是链表的"第一斧"：假头。如下所示：
java
class MyLinkedList {
// 实现单链表
// 1. 假设链表中的所有节点都是 0-index的。
class ListNode {
public int val = 0;
public ListNode next = null;
public ListNode() {}
public ListNode(int x) {
val = x;
}
}
private ListNode dummy = new ListNode();
private ListNode tail = dummy;
private int length = 0;
/** Initialize your data structure here. */
public MyLinkedList() {
}
private ListNode getPreNode(int index) {
ListNode front = dummy.next;
ListNode back = dummy;
for (int i = 0; i < index; i++) {
back = front;
front = front.next;
}
return back;
}
// 获取链表中第 index 个节点的值。如果索引无效，则返回-1。
public int get(int index) {
if (index < 0 || index >= length) {
return -1;
}
return getPreNode(index).next.val;
}
// 在链表的第一个元素之前添加一个值为 val 的节点。
// 插入后，新节点将成为链表的第一个节点。
public void addAtHead(int val) {
ListNode p = new ListNode(val);
p.next = dummy.next;
dummy.next = p;
// NOTE change tail
if (tail == dummy) {
tail = p;
}
length++;
}
// 将值为 val 的节点追加到链表的最后一个元素。
public void addAtTail(int val) {
tail.next = new ListNode(val);
tail = tail.next;
length++;
}
// 在链表中的第 index 个节点之前添加值为 val 的节点。
// 1. 如果 index 等于链表的长度，则该节点将附加到链表的末尾。
// 2. 如果 index 大于链表长度，则不会插入节点。
// 3. 如果index小于0，则在头部插入节点。
public void addAtIndex(int index, int val) {
if (index > length) {
return;
} else if (index == length) {
addAtTail(val);
return;
} else if (index <= 0) {
addAtHead(val);
return;
}
ListNode pre = getPreNode(index);
ListNode p = new ListNode(val);
p.next = pre.next;
pre.next = p;
// NOTE: here tail has been changed
length++;
}
// 如果索引 index 有效，则删除链表中的第 index 个节点。
public void deleteAtIndex(int index) {
if (index < 0 || index >= length) {
return;
}
ListNode pre = getPreNode(index);
// NOTE: delete -> change tail
if (tail == pre.next) {
tail = pre;
}
length--;
pre.next = pre.next.next;
}
}此外，关于链表，我们还需要掌握另外的"两板斧"。这里我已经将知识点整理如下：
树
在《06 | 树：如何深度运用树的遍历？》中，我们深入探讨了三种遍历，并且发现只要我们掌握这三种遍历的模板代码，就能够轻松解决二叉树问题。
在这一讲中，我们需要熟练掌握三种遍历的代码模板有 6 个：
前序遍历的递归实现与栈的实现
中序遍历的递归实现与栈的实现
后序遍历的递归实现与栈的实现
下面我们分别整理一下。
前序遍历
采用递归的前序遍历的代码如下（解析在注释里）：
java
void preOrder(TreeNode root, List<Integer> ans) {
// 边界处理：如果树为空，那么不需要处理
if (root != null) {
// 先访问根结点
ans.add(root.val);
// 再分别访问左子树
preOrder(root.left, ans);
// 再访问右子树
preOrder(root.right, ans);
}
}使用栈来实现的前序遍历的代码如下（解析在注释里）：
java
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
// 用来进行递归的栈
Stack<TreeNode> s = new Stack<>();
// 用来存放遍历的结果，不算在空间复杂度里面
List<Integer> ans = new ArrayList<>();
// 开始利用栈来进行遍历
while (root != null || !s.empty()) {
// 模拟递归的压栈过程
while (root != null) {
s.push(root);
ans.add(root.val);
root = root.left;
}
// 当无法压栈的时候，将root.right进行压栈
root = s.peek();
s.pop();
root = root.right;
}
return ans;
}
}中序遍历
采用递归的中序遍历代码如下（解析在注释里）：
java
void preOrder(TreeNode root, List<Integer> ans) {
if (root != null) {
// 先遍历左子树
preOrder(root.left, ans);
// 然后遍历中间的根结点
ans.add(root.val);
// 最后遍历右子树
preOrder(root.right, ans);
}
}采用非递归的中序代码（解析在注释里）：
java
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
Stack<TreeNode> s = new Stack<>();
List<Integer> ans = new ArrayList<>();
// 注意这里的判断条件，需要root 或 stack非空
while (root != null || !s.empty()) {
// 往左边走，连续入栈，直到不能再走为止
while (root != null) {
s.push(root);
root = root.left;
}
// 到达了最左边，把结点弹出来，进行遍历
root = s.peek();
s.pop();
ans.add(root.val);
// 转向右子树
root = root.right;
}
// 返回遍历的结果
return ans;
}
}后序遍历
采用递归实现的后序遍历代码模板如下（解析在注释里）：
java
void postOrder(TreeNode root, List<Integer> ans) {
if (root != null) {
// 先遍历左子树
postOrder(root.left, ans);
// 最后遍历右子树
postOrder(root.right, ans);
// 然后遍历中间的根结点
ans.add(root.val);
}
}采用非递归的后序遍历代码如下（解析在注释里）：
java
class Solution {
public List<Integer> postorderTraversal(TreeNode t) {
// 存放遍历的结果
List<Integer> ans = new ArrayList<>();
// pre表示遍历时前面一个已经遍历过的结点
TreeNode pre = null;
Stack<TreeNode> s = new Stack<>();
// 如果栈中还有元素，或者当前结点t非空
while (!s.isEmpty() || t != null) {
// 顺着左子树走，并且将所有的元素压入栈中
while (t != null) {
s.push(t);
t = t.left;
}
// 当没有任何元素可以压栈的时候
// 拿栈顶元素，注意这里并不将栈顶元素弹出
// 因为在迭代时，根结点需要遍历两次，这里需要判断一下
// 右子树是否遍历完毕
t = s.peek();
// 如果要遍历当前结点，需要确保右子树已经遍历完毕
// 1. 如果当前结点右子树为空，那么右子树没有遍历的必要
// 需要将当前结点放到ans中
// 2. 当t.right == pre时，说明右子树已经被打印过了
// 那么此时需要将当前结点放到ans中
if (t.right == null || t.right == pre) {
// 右子树已经遍历完毕，放到ans中。
ans.add(t.val);
// 弹栈
s.pop();
// 因为已经遍历了当前结点，所以需要更新pre结点
pre = t;
// 已经打印完毕。需要设置为空，否则下一轮循环
// 还会遍历t的左子树。
t = null;
} else {
// 第一次走到t结点，不能放到ans中，因为t的右子树还没有遍历。
// 需要将t结点的右子树遍历
t = t.right;
}
}
return ans;
}
}【面试建议】在面试的时候，大部分情况都应该优先写递归的代码，除非面试官特别要求你必须使用"非递归"来实现。主要有以下几点原因：
递归代码更加简单，因此不容易出错；
不要为了"炫技"展示"非递归"代码；
如果我们要进行二叉树上的搜索、DP、二分等情况的时候，"非递归"的代码往往会增加代码的复杂度，面试的时候不容易完全写对。
并查集
虽然并查集的代码模板只有一个，但是涉及的知识点却不少，这里我们将重点的内容浓缩在下面这张图里：
最后，我们给出并查集的代码模板如下（解析在注释里）：
java
class UF {
// 并查集数组
int[] F = null;
// 记录并查集中集合的个数
int count = 0;
// 记录集合中点的个数，比如要知道i所在集合的点有多少个: C[Find(i)]
// 注意：这里不能直接使用C[i]
// 因为只有根结点的统计才是正确的
int[] Cnt = null;
// 并查集的初始化
void Init(int n)
{
F = new int[n];
Cnt = new int[n];
for (int i = 0; i < n; i++) {
F[i] = i;
Cnt[i] = 1;
}
count = n;
}
int Find(int x)
{
if (x == F[x]) {
return x;
}
F[x] = Find(F[x]);
return F[x];
}
void Union(int x, int y)
{
int xpar = Find(x);
int ypar = Find(y);
// 将x所在集合，合并到y所在集合
if (xpar != ypar) {
F[xpar] = ypar;
// y集合里面的个数要增加
Cnt[ypar] += Cnt[xpar];
count--;
}
}
int Size(int i) {return Cnt[Find(i); }
}总结
在这一讲中，我们通过整理代码模板，将"第 01 讲" 到"第 07 讲"学习的所有知识点都整理好了。这样你复习起来是不是压力要小很多呢。下面我再和你分享两个代码模板的"小秘密"。
模板代码要精练
其实在整理模板的时候，要尽量将代码压缩得越短越好（指的并不是不换行），代码压缩得短，有以下好处：
如果是自己熟悉的代码，在需要记忆的情况下，越短越好记；
较短的代码可以更精练，一眼看上去没有那么大的心理压力。
比如就我自己而言，在复习并查集的代码时，就经常使用下面这段更短的代码：
java
int Find(int x) { return x == F[x] ? x : F[x] = Find(F[x]); }
void Union(int x, int y) { F[find(x)] = find(y); }自己整理可复用的代码模版
和你分享一下自己整理的模板的好处。主要是基于以下两点原因。
1. 变量的命名要有规律，而这些规律都是自己平时约定使用的，当你复习代码时会更熟练，比如：
1）返回值一律设置为 ans 或者 ret；
2）遍历下标设置为 i,j,k；
3）长度变量设置为 len。
2. 同一个算法往往有很多种写法，自己的写法会更熟悉，而且可以不断迭代和复用。
所以，本讲的练习题，就是希望你能把"第 01 讲"到"第 07 讲"刷过的题的代码整理成模板。当临近面试，你只需要对着思维导图和代码模板过一下思路就可以了。
这一讲我们就介绍到这里。下一讲介绍《23 | 算法模板：如何让高频算法考点秒变默写题？》，让我们继续前进。