数据结构进阶：单调栈、并查集与字符串哈希

概述

本文介绍基础算法篇中的数据结构进阶内容，主要包括单调栈、单调队列、并查集（含扩展域与带权）、字符串哈希以及 Trie 树。

数据结构进阶

单调栈

里面存储的是单增或者单减的栈元素。

应用：

1. 寻找当前元素左侧，离它最近且比它大的元素位置。
2. 寻找当前元素左侧，离它最近且比它小的元素位置。
3. 寻找当前元素右侧，离它最近且比它大的元素位置。
4. 寻找当前元素右侧，离它最近且比它小的元素位置。

// 寻找当前元素左侧，离它最近，并且比它大的元素在哪
int a[N]; // 已存好数据
int ret[N]; // 存答案
std::stack<int> st; // 维护一个单调递减的栈，里面存的是下标
for (int i = 1; i <= n; i++) {
    // 栈里面小于等于 a[i] 的元素全部出栈
    while (st.size() && a[st.top()] <= a[i]) st.pop();
    // 此时栈顶元素存在，栈顶元素就是所求结果
    if (st.size()) ret[i] = st.top();
    st.push(i);
}

// 寻找当前元素右侧，离它最近，并且比它大的元素在哪
// 改成 for(int i = n; i >= 1; i--) 即可

// 寻找当前元素左侧，离它最近，并且比它小的元素在哪
int a[N]; // 已存好数据
int ret[N]; // 存答案
std::stack<int> st; // 维护一个单调递增的栈，里面存的是下标
for (int i = 1; i <= n; i++) {
    // 栈里面大于等于 a[i] 的元素全部出栈
    while (st.size() && a[st.top()] >= a[i]) st.pop();
    // 此时栈顶元素存在，栈顶元素就是所求结果
     (st.()) ret[i] = st.();
    st.(i);
}