线性数据结构 - Queue、Stack、Hash
树型数据结构 - Heap / Priority Queue、TreeMap
BFS的主要数据结构是 Queue
DFS的主要数据结构是 Stack
目录：
-
-
什么是数据结构
1.1 分类
1.2 什么是数据结构？
-
-
-
队列 Queue
2.1 基础知识
2.2 相关题目 - BFS相关的题目
-
-
-
栈 Stack
3.1 基础知识
3.2 相关题目 - 非递归实现DFS的主要数据结构
3.3 min-stack 带最小值操作的栈（12 in lintcode）
3.4 largest-rectangle-in-histogram 直方图最大矩阵覆盖（122 in lintcode）
3.5 maximal-rectangle 最大矩阵（510 in lintcode）
-
-
- 哈希表 Hash - 见相关笔记
-
- 树型数据结构 - 见相关笔记，包括Heap / Priority Queue、TreeMap
1. 什么是数据结构 -
1.1 分类
1.2 什么是数据结构？
1). 数据结构 = 集合 + 集合上的若干操作
2). 可以在链表上进行二分法吗？
不可以，因为二分法复杂度为O(n)，（O(n) = O(n/2) + O(1）） O(1)链表不能达到
3). 定义一种数据结构，必须要定义该数据结构支持的操作，以及操作的时间复杂度是什么
4). 所有的数据结构落实到底层数据结构均为2种：
- 数组（连续空间）
- 链表（离散空间）
2. 队列 Queue -
2.1 基础知识
1). 先进先出。
2). 支持的操作： O(1) Push / O(1) Pop / O(1) Top
3). BFS的主要数据结构。多做BFS的题目就可以了。
4). 实现队列的话，数组和链表均可，linkedList更常用，c++中的vector、java中的ArrayList，是动态数组，每次空间不够时乘2。还可以使用循环数组实现队列。
5). 建议用数组和链表把队列都实现一遍。
2.2 相关题目 - BFS相关的题目
3. 栈 Stack - 非递归实现DFS的主要数据结构
3.1 基础知识
1). 后进先出，在末尾操作
2). 支持的操作： O(1) Push / O(1) Pop / O(1) Top
3). DFS非递归实现的主要数据结构。多做BFS的题目就可以了。
4). 建议用数组和链表把队列都实现一遍。
3.2 相关题目 - 非递归实现DFS的主要数据结构
3.3 min-stack 带最小值操作的栈（12 in lintcode）
1.题目
http://www.lintcode.com/zh-cn/problem/min-stack/
http://www.jiuzhang.com/solution/min-stack/
实现一个带有取最小值min方法的栈，min方法将返回当前栈中的最小值。
你实现的栈将支持push，pop 和 min 操作，所有操作要求都在O(1)时间内完成。
样例
如下操作：push(1)，pop()，push(2)，push(3)，min()， push(1)，min() 返回 1，2，1
2.代码
1). 典型的数据结构的实现题
2). 分析：
2个stack，保存最小值得变化序列。每次push、pop时，需要更新存最小值的栈。
3). 代码
3.4 largest-rectangle-in-histogram 直方图最大矩阵覆盖（122 in lintcode）
1.题目
http://www.lintcode.com/zh-cn/problem/largest-rectangle-in-histogram/
http://www.jiuzhang.com/solution/largest-rectangle-in-histogram/
Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].
The largest rectangle is shown in the shaded area, which has area = 10 unit.
样例
给出 height = [2,1,5,6,2,3]，返回 10
2.思路 &代码
1). 分析：
最多有n2种组合，理论上复杂度可以降到n2。
如果复杂度为多项式（n^2 ，n3，n4… ），则一定不用dp，dp适合复杂度为2^n的。
2). 求解
解法1：-时间复杂度O（n^2）,会超时 TLE
A.两个for循环，startIndex，endIndex。
挪动endIndex时，记录最小值，并将计算到的面积与全局面积比较。
B. 出现TLE的可能情况
- 复杂度太高；
- 死循环 （如二分法或者链表等复杂度不高的元素出现超时，一定是死循环了）
解法2：- O(n)
A. nlogn的可能算法有以下三种：
- Divide & Conqure, O(n) 分为2部分，递归，如merge sort
- 先排序，再用O(n)搞定
- for一遍，内部支持logn的数据结构，如heap/priority queue / TreeMap 求最大最小值
B. 本题使用 单调栈，复杂度是O(n)
- 单调栈可以找到某个数左边（右边）第一个比他小的数
3.5 maximal-rectangle 最大矩阵（510 in lintcode）
1.题目
http://www.lintcode.com/zh-cn/problem/maximal-rectangle/
http://www.jiuzhang.com/solution/maximal-rectangle/
给你一个二维矩阵，权值为False和True，找到一个最大的矩形，使得里面的值全部为True，输出它的面积
样例
给你一个矩阵如下
[
[1, 1, 0, 0, 1],
[0, 1, 0, 0, 1],
[0, 0, 1, 1, 1],
[0, 0, 1, 1, 1],
[0, 0, 0, 0, 1]
]
输出6
2.思路 & 代码
此题是之前那道的 Largest Rectangle in Histogram 直方图中最大的矩形 的扩展，这道题的二维矩阵每一层向上都可以看做一个直方图，输入矩阵有多少行，就可以形成多少个直方图，对每个直方图都调用 Largest Rectangle in Histogram 直方图中最大的矩形 中的方法，就可以得到最大的矩形面积。那么这道题唯一要做的就是将每一层构成直方图，由于题目限定了输入矩阵的字符只有 ‘0’ 和 ‘1’ 两种，所以处理起来也相对简单。方法是，对于每一个点，如果是‘0’，则赋0，如果是 ‘1’，就赋 之前的height值加上1。具体参见代码如下：
class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
if (matrix.empty() || matrix[0].empty()) return 0;
int res = 0, m = matrix.size(), n = matrix[0].size();
vector<int> height(n + 1, 0);
for (int i = 0; i < m; ++i) {
stack<int> s;
for (int j = 0; j < n + 1; ++j) {
if (j < n) {
height[j] = matrix[i][j] == '1' ? height[j] + 1 : 0;
}
while (!s.empty() && height[s.top()] >= height[j]) {
int cur = s.top(); s.pop();
res = max(res, height[cur] * (s.empty() ? j : (j - s.top() - 1)));
}
s.push(j);
}
}
return res;
}
};