数据结构

单调栈（Monotone Stack）

常见模型：找出每个数左边离它最近的比它大/小的数

单调递增栈

保证栈内元素单调递增。（从栈顶到栈底）

  • 只有比栈顶大的元素才能直接进栈
  • 首先先将栈中比当前元素大的元素出栈
    • 出栈时，新元素是出栈元素向后找第一个比其小的元素
    • 所有出栈后，栈顶元素是新元素向前找第一个比其小的元素
  • 再将当前元素出栈
1
2
3
4
5
6
7
8
9
10
11
12
stack<int> st;

for(int i = 0; i < n; i++){
	while(!st.empty() && st.top >= nums[i]){ // 判断栈顶是否符合单调递增关系
        // 新元素是出栈元素向后找第一个比其小的元素
        st.pop();
    }  
    // 栈顶元素是新元素向前找第一个比其小的元素
    st.push(nums[i]);
    
    // 具体逻辑.. 
}

830. 单调栈 - AcWing题库

单调递减栈

栈内元素递减

（同上）

单调队列

常见模型：找出滑动窗口中的最大值/最小值

1
2
3
4
5
6
7
8
9
deque<Node> que;

for(int i=0;i<n;i++){
    while(!que.empty() && check_head(que.front())) que.pop_front(); // 判断队头是否滑出窗口
    while(!que.empty() && check(que.back(), i)) que.pop_back();   // 判断队尾是否符合单调
    que.push_back(i);
    
    // 具体逻辑
}

154. 滑动窗口 - AcWing题库

并查集

朴素并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
int p[N]; //存储每个点的祖宗节点

// 返回x的祖宗节点
int find(int x){
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ ) p[i] = i;

// 合并a和b所在的两个集合：
p[find(a)] = find(b);

维护Size的并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量
int p[N], size[N];

// 返回x的祖宗节点
int find(int x){
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ ){
    p[i] = i;
    size[i] = 1;
}

// 合并a和b所在的两个集合：
size[find(b)] += size[find(a)];
p[find(a)] = find(b);

维护到祖宗节点距离的并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int p[N], d[N];
//p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离

// 返回x的祖宗节点
int find(int x)
{
    if (p[x] != x)
    {
        int u = find(p[x]);
        d[x] += d[p[x]];
        p[x] = u;
    }
    return p[x];
}

// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ )
{
    p[i] = i;
    d[i] = 0;
}

// 合并a和b所在的两个集合：
p[find(a)] = find(b);
d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量

KMP 字符串匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
	// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
求模式串的Next数组：
for (int i = 2, j = 0; i <= m; i ++ )
{
    while (j && p[i] != p[j + 1]) j = ne[j];
    if (p[i] == p[j + 1]) j ++ ;
    ne[i] = j;
}

// 匹配
for (int i = 1, j = 0; i <= n; i ++ )
{
    while (j && s[i] != p[j + 1]) j = ne[j];
    if (s[i] == p[j + 1]) j ++ ;
    if (j == m)
    {
        j = ne[j];
        // 匹配成功后的逻辑
    }
}

Trie树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int son[N][26], cnt[N], idx;
// 0号点既是根节点，又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量

// 插入一个字符串
void insert(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
    cnt[p] ++ ;
}

// 查询字符串出现的次数
int query(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

指针形式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
struct TrieNode{
    bool isend;
    TrieNode* child[26];
};
TrieNode *root;

Trie() {
    root = new TrieNode();
}

void insert(string word) {
    int len = word.size();
    TrieNode* cur = root;
    for(int i = 0; i<len; i++){
        int u = word[i]-'a';
        if(!cur->child[u]) cur->child[u] = new TrieNode();
        cur = cur->child[u];
    }
    cur->isend = true;
}

bool search(string word) {
    int len = word.size();
    TrieNode* cur = root;
    for(int i = 0; i<len; i++){
        int u = word[i] - 'a';
        if(!cur->child[u]) return false;
        cur = cur->child[u];
    }
    return cur->isend;
}