单调栈

一、什么是单调栈？

单调栈（Monotonic Stack）是一种特殊的栈，在栈的「先进后出」基础上，要求「从栈顶到栈底的元素是单调的（递增或递减）」。

与普通栈不同，单调栈的元素是按照特定的单调性（递增或递减）排列的：

1
2
3
4
5
6
7

 普通栈        单调栈

|     |       |     |                    
|     |       |     |                     
|  3  |       |  1  |    <-- 栈顶
|  1  |       |  2  |                 
|__2__|       |__3__|    <-- 栈底

按照单调栈的元素是按照特定的单调性，可分为两种类型：

二叉搜索树

一、结构定义

二叉搜索树（binary search tree），也称为二叉查找树，是一种二叉树，同时还满足了以下的条件：

1. 对于根节点，左子树中所有节点的值 < 根节点的值 < 右子树中所有节点的值
2. 任意节点的左、右子树也是二叉搜索树

相比于普通二叉树，二叉搜索树的节点之间带有大小关系，这使得二叉搜索树可以支持快速的查找、插入、删除操作。

二叉树遍历

二叉树常见的遍历方式包括层序遍历、前序遍历、中序遍历和后序遍历等。

一、层序遍历

层序遍历（Level-Order Traversal）从顶部到底部逐层遍历二叉树，并在每一层按照从左到右的顺序访问节点。

层序遍历本质上属于广度优先遍历。

二叉树

一、什么是二叉树？

1.1 二叉树的定义

• 由一系列节点组成的有限集合，每个节点都有且仅有 2 个子节点（空节点也算在内）
• 每个子节点构成一棵子树，并且子树之间没有交集

1.2 二叉树的结构

队列

一、结构特性

基本定义：

• 队列是一种遵循先入先出规则的线性数据结构

主要特点：

• 数据是先进先出，后进后出
• 只允许从队首入队，从队尾出队

队列的两端分别称为「队首」和「队尾」。

栈

一、结构特性

基本定义：

• 栈是一种遵循先入后出的逻辑的线性数据结构

主要特点：

• 数据是先入后出，后入先出
• 只允许在栈的一端操作数据

栈的两端分别称为“栈顶”和“栈底”：

链表

一、结构特性

链表是通过指针将一系列离散的内存块串联在一起的线性表数据结构。

主要特点：

• 线性表数据结构
• 离散的内存空间
• 指针关联
• 动态申请内存空间

数组

一、结构特性

基本定义：

• 数组是存放在连续内存空间上的相同类型数据的线性表结构

主要特点：

• 线性表数据结构
• 连续的内存空间
• 相同类型的数据

三向快速排序

一、算法描述

1.1 核心思想

• 三分，选取一个分区值，将数据分割成 3 部分：小于、等于、大于
• 递归，对小于大于两部分继续排序，不断选点分割数据，直到无法分割为止
• 整个过程和快速排序类似，只是原来的一个分区点变成了一个区间而已

1.2 细节解释

二分插入排序

一、算法描述

1.1 核心思想

• 数据分为已排序区间和未排序区间
• 从未排序区间取出元素，通过二分法找到合适的位置，插入到已排序区间中
• 插入已排序区间时，同时要保证已排序区间的有序性

总体上和插入排序差不多，只是在插入的时候，使用二分查找来找到合适的插入位置。

1.2 细节解释