【数据结构】线性数据结构

int BFS()
{
	queue<int> q;
    unordered_set<节点或状态> map;	//可选，看是否需要重复入队
    int step = 0;
    q.push(根节点或状态);
    while(!q.empty())
    {
        ++step;
        int size = q.size();
        for(int i = 0; i < size; i++)	//遍历当前层所有节点并扩展相邻节点
        {
            节点或状态 cur = q.front();	//取队列头节点
            if(cur == 目标节点或状态)	return step;
            for(节点 x : cur的所有相邻节点)
            {
                if(map.count(x)) continue;	//判断是否已经访问过，可选
                q.push(x);
                map.insert(x);	//可选
            }
            q.pop();
        }
    }
    return step;
}

4、栈

深搜DFS

一般能用广搜的也能用深搜，但是深搜不能保证是最短路径或者最小数量，深搜还用于二叉树的前中后序遍历。
钥匙和房间
 图像渲染
以及上面可以用BFS做的题

DFS模板（非递归，类似于上面的BFS）

bool DFS(节点 root，节点 target)
{
	stack<int> s;
    unordered_set<节点> visited;	//可选，看是否需要重复入栈
    s.push(root);
    visited.insert(root);
    while(!s.empty())
    {
        节点 cur = q.top();	//取栈顶节点
        if(cur == target) return true;
        for(节点 x : cur的所有相邻节点)
        {
            if(visited.count(x)) continue;	//判断是否已经访问过，可选
            q.push(x);
            visited.insert(x);	//可选
        }
        q.pop();
    }
    return false;
}

DFS模板（递归）

bool DFS(节点 root，节点 target, unordered_set<节点>& visited)
{
    if(root == target) return true;
    for(节点 x : root的所有相邻节点)
    {
        if(visited.count(x)) continue;	//判断是否已经访问过，可选
        visited.insert(x);	//可选
        if(DFS(x,target,visited)) return true;   
    }
    return false;
}

单调栈

单调栈也是一种重要的数据结构，在实际解题中经常用到，简单来说单调栈内的元素保证是严格单调递增或递减的，如果一个新的元素和栈顶元素不满足这种单调关系，就将栈顶元素出栈并进行一定的操作，直到满足单调关系，将新元素入栈。

之前的题目中也遇到过一些比较简单的单调栈问题，这里以两道困难题目加深对单调栈的理解。

柱状图中最大的矩形

最大矩形

但这两道题较为困难，能够加深对单调栈的理解。柱状图中的最大矩形的思路简单来说就是遍历每一根柱子，分别找到其左边和右边离它最近的高度低于它的柱子作为左右边界，在这两个边界范围内的所有柱子的高度都高于当前柱子，因此所形成的矩形面积就是当前柱子高度乘以边界长度。寻找柱子边界的过程就是利用单调栈实现的，并且优化过后只需要遍历一次就可以找到左边界和右边界。关于单调栈的思路如何得到以及优化具体细节可以查看柱状图中最大的矩形官方题解。

最大矩形是一道更为困难的题目，但是如果理解了柱状图问题，再看最大矩形就不是很困难了。因为我们可以对矩阵每一行的每一个位置都求出这个位置上方连续的1的个数（包含这个位置本身），这样每一行都形成了一个柱状图，再按照柱状图的解法计算最大矩形面积即可，遍历完矩阵所有行也就得到了全局最大矩形。更多细节在代码中：

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        vector<int> height(n, 0);     //记录每一行每个位置上方连续的1的个数（包含本身）
        int ans = 0;
        for(int i = 0; i < m; ++i)
        {
            vector<int> left(n), right(n, n);	//每一行遍历开始都要重置right数组的初始值为n
            //计算每个格子上方连续1的个数，形成柱状图
            for(int j = 0; j < n; ++j)
            {
                if(i == 0)
                {
                    height[j] = matrix[i][j] - '0';
                }
                else
                {
                    height[j] = matrix[i][j] == '1' ? height[j] + 1 : 0;
                }
            }
            //计算直到当前行的柱状图最大矩形
            stack<int> mono;
            for(int j = 0; j < n; ++j)
            {
                while(!mono.empty() && height[mono.top()] >= height[j])	//注意更新右边界的判断条件是'>='
                {
                    right[mono.top()] = j;
                    mono.pop();
                }
                left[j] = mono.empty() ? -1 : mono.top();
                mono.push(j);
            }
            //更新结果
            for(int j = 0; j < n; ++j)
            {
                ans = max(ans, height[j] * (right[j] - left[j] - 1));
            }
        }
        return ans;
    }
};

LycTechStack

【数据结构】线性数据结构

线性数据结构

1、数组和字符串

二分查找

首尾双指针

快慢双指针

滑动窗口

字符串匹配KMP算法

二维数组

2、链表

递归

快慢指针

经典问题

3、队列

广搜BFS

4、栈

深搜DFS

单调栈