%%
# 纲要
> 主干纲要、Hint/线索/路标
# Q&A
#### 已明确
#### 待明确
> 当下仍存有的疑惑
**❓<font color="#c0504d"> 有什么问题？</font>**
# Buffer
## 闪念
> sudden idea
## 候选资料
> Read it later
%%
# 栈
## 栈混洗
**==栈混洗==**：将栈 A 中的 **$n$ 个元素**经 "**中转栈 S**" 再全部转入**栈 B**，在栈 B 得到一个**同样长度为 $n$ 的序列**称为栈混洗，如下图所示：
> [!NOTE] 上述过模型等价于： 对于 n 个值和一个栈，给定一个 **==入栈操作序列 A==**，能得到**多少种可能的 "==出栈操作序列 B=="**。
>
<br>
### 栈混洗相关的问题
- （1）**对于长度为 n 的序列，可能得到的栈混洗结果有多少种**？（即栈 B 中可能得到的不同序列数量）
- => 即给定一个 **==入栈操作序列 A==**，能得到**多少种可能的 "==出栈操作序列 B=="**。
- （2）**已知序列 A**，判断**一个给定序列 B**，是否为 A 的合法 "**栈混洗结果**"。
- => 即给定一个 **==入栈操作序列 A==** 以及一个 "**出栈操作序列 B**"，**判断 B 是否可能成立**。
> [!example] 例题： [[99-题解/leetcode/lc-946 验证栈序列|lc-946 验证栈序列]] ^a26z5s
<br>
### （1）栈混洗的可能结果
记**栈混洗方案数**为 $SP(n)$，显然 $SP(n)\le n!$ （**小于等于 n 个元素全排列数量**）。
#### 推导分析
首先将栈 A 中 **第一个元素**（1 号）推入中转栈 S 中，**分析 1 号元素被从 S 中弹出并推入栈 B 中的可能情况**。
> 
设 1 号元素入栈 B 后，**栈 B 中在其之前共有 `k-1` 个元素**，由于 1 号元素是 S 的栈底元素，因此栈 S 为空，栈 A 中则剩余 `n-k` 个元素。
此时**栈 B 中的前 `k-1` 个元素**和 A 中的 **`n-k `个元素的栈混洗数**是彼此独立的，因此总的栈混洗方案数 = $SP(k-1)\cdot SP(n-k)$：
- 得到栈 B 中的前 `k-1` 个元素共有 $SP(k-1)$ 种可能情况
- 将栈 A 中的剩余`n-k` 个元素最终转移到 B 中则仍有 $SP(n-k)$ 种情况
因此，对应于**1 号元素作==为第 $k$ 个元素被推入栈 B== 中的情况**，栈混洗总数为 $SP(k-1)*SP(n-k)$ 种。
而 $k$ 所有可能的取值是 $1\sim n$，因此对 A 中的 $n$ 个元素，**所有可能的栈混洗总数**为：
$
\large SP(n)=\sum_{k=1}^nSP(k-1)*SP(n-k)
$
由此得到一个递推式。平凡情况 $SP(1)=1$。
#### 结果
该递推式的解 $SP(n)$ 即为**卡特兰数 $Catalan(n)$** ：
$
Catalan(n)=\Large \frac{(2n)!}{(n+1)!\cdot n!}
$
> 
<br>
### （2）判断一个给定序列是否为合法的栈混洗结果
##### 理论分析
**任意三个元素能否按某次序出现在混洗中，与其它元素无关**。
> 
对于**原始栈 A 中的三项元素**（对应下标 $1\le i < j <k \le n$），栈 B 中的栈混洗结果**必不可能存在** 下列情况：
$
\large [\dots,k,\dots,i,\dots,j,\dots>
$
该条件是 **==充分必要条件==，所有不存在上述模式的序列，一定是正确的栈混洗结果**。
> [!说明] 若最终栈混洗结果里 **`k` 能位于 `i` 与 `j` 之前**，就意味着当 `k` 进入栈 B 时，**`i` 与 `j` 一定在中转栈 `s` 中**，所以最后必然应当是 `j` 先出栈， `j` 位于 `i` 之前。
##### 实际验证方法
根据给定的**入栈操作序列 A** 以及 **出栈操作序列 B**，用一个栈**模拟入栈以及出栈过程**，看看是否最后能得到空栈。
![[00-数据结构与算法笔记/数据结构/栈#^a26z5s]]
## 栈的典型应用
栈的典型应用：
> 
### 括号匹配问题
"**括号匹配**" 问题即 "检查给定括号字符串**是否有==无法被匹配==的多余左括号或右扩号**"，只需考虑**两方面**。
记左、右括号数量分别为 `l_cnt`，`r_cnt`，初始为 0：
1. **从左到右遍历==过程中==**， `l_cnt >= r_cnt` 必须始终成立，否则表明**存在无法匹配的==多余右扩号==**；
2. **遍历==结束后==**，若 `l_cnt > r_cnt`，说明存在**无法匹配的==多余左括号==**。
该过程可只用一个变量 `score` 记录 "**剩余未匹配的==左括号数量==**"，初始为 0，对左括号则 `+1`，对右扩号则 `-1`。
1. **从左到右遍历==过程中==**，若 `score < 0` 说明**右扩号多余**，非法；
2. **遍历==结束后==**，若 `score != 0` 说明**左括号多余**，非法。
> [!example]
> 
```cpp
// 括号匹配
// 注: 采用栈可以便捷地推广至多中括号并存的情况, 而此时使用多个计数器是行不通的.
// 方法一: 基于栈的实现
// 栈中记录已扫描的部分, 只记录左括号.
// 顺序扫描表达式, 遇见左括号则入栈, 遇见右括号则出栈.
bool bracket_matching(string expr) {
stack<char> s; //使用栈记录 "已发现但尚未匹配的左括号"
for (char ch : expr) {
if (ch == '(') {
s.push(ch;
} else {
if (!s.empty()) { // 遇右括号时栈非空, 弹出匹配的右括号
s.pop();
} else {
return false; // 遇右括号时栈已空，必不匹配
}
}
}
return s.empty();
}
// 方法二: 无需栈, 模拟栈计数.
// 如果仅存在一种括号, 只需一个计数器记录任何时刻"栈的size"即可, 也即"剩余未匹配"的左括号数量
bool bracket_matching(string expr) {
int score = 0;
for (char ch : expr) {
if (ch == '(') {
++score;
} else if (score > 0) {
--score;
} else {
return false;
}
}
return score == 0;
}
```
%%
### 中缀表达式求值
- 用一个栈来保存**已扫描过的部分**，在所有已扫描过的部分中：
- 一部分是经过判断能够即时处理的，即"done"的部分（在局部具有较高优先级，能够被计算的部分）
- 已扫描过，**还不足以判断的部分，则被栈缓冲起来**。
### 逆波兰表达式求值
- 中缀表达式转逆波兰表达式
- 逆波兰表达式求值
参见 vscode 代码
%%
---
<br><br>
<br>
# 单调栈
## 定义 & 性质
**单调栈**：**栈中元素==从栈底至栈顶==单调==递增 or递减==的栈**
#### 维护单调栈
遍历数组的过程中，若**即将入栈的新元素==相较于栈顶元素==不满足单调性**，则**将栈顶元素持续出栈**，直到当前元素较栈顶元素而言符合单调性，将当前元素入栈。
- 栈底->栈顶单调**递增**栈：只有比栈顶元素大的才能入栈
- 栈底->栈顶单调**递减**栈：只有比栈顶元素小的才能入栈
> [!NOTE] 要点：对于即将入栈的新元素，**持续弹出==栈顶元素==** 直到**新元素入栈后作为栈顶元素仍满足单调性**。
<br>
## 应用场景
> ❓<font color="#c00000">单调栈有哪些应用场景？</font>
1. 为**每个元素**求其 **左右侧 =="最近"== 的 ==相等/更大/更小== 元素**；
2. 求数组中满足 **`i < j && arr[i] < arr[j]`** 的**最远距离** `j-i`。
> [!faq] <font color="#c00000">❓如何为每个元素找其左右侧 "==最远==" 的一项更大更小元素？</font>
>
> ![[00-数据结构与算法笔记/专题总结/前缀和与差分数组#（1）为数组中每个元素获取其左右侧"最远"的 "更大/更小元素"|前缀和与差分数组]]
<br><br>
## （1）求解 "每个元素左侧或右侧最近的更大/更小元素"
> 两种实现方式的模版参见代码库 `monotionic_stack.cpp`
具体实现上有两种写法，差别在于对 **"单调栈" 中所保存元素的定义**不同：
- 方式一：栈中保存 "**==已求得左侧或右侧最近更大/更小元素==的元素**"（推荐❇️）
- 方式二：栈中保存 "**==未求得左侧或右侧最近更大/更小元素==的元素**"
### 两种实现定义方式
| | 方式一 | 方式二 |
| ----------------- | -------------------------------------------------------------------------------------------------------------------- | -------------------------------------------------------------------------------------------------------------------- |
| 栈中保存的元素 | **==已求得==**左侧或右侧最近更大/更小值的元素 | **==未求得==**左侧或右侧最近更大/更小值的元素 |
| 栈中元素单调性 | **严格**单调（无重复值） | 非严格单调（允许重复值） |
| 遍历顺序 | **求哪一侧**的 "最近更小/更大" 元素，<br>就**从==同一侧==**开始遍历 | **求哪一侧**的 "最近更小/更大" 元素，<br>就**从==另一侧==**开始遍历 |
| 何时得到答案 | 元素 **==入栈==** 时 | 元素 **==出栈==** 时 |
| 得到答案的主体 | **==当前新入栈==元素** | **==出栈==元素** |
| 主体左侧或右侧的最近更小/更大元素 | **栈中其下方的元素** | **当前==待入栈==元素** |
| 栈的使用 | 在每个元素 "**==入栈==**" 时为其求得 "**左侧（或右侧）** 最近**更小/更大**元素"，<br>而 "**==出栈==**" 时将得到其 **右侧（或左侧）** 的最近 "**==相等==** 或更小/更大" 元素 | 在每个元素 "**==出栈==**" 时为其求得 "**左侧（或右侧）** 最近**更小/更大**元素"，<br>而 "**==入栈==**" 时将得到其 **右侧（或左侧）** 的最近 "**==相等==** 或更小/更大" 元素 |
在第二种方式下，由于**每个元素直到其被 "出栈" 时才能求得其的 "左侧或右侧最近最大/更小" 元素**，因此 **==最后需要对栈中剩余的元素单独处理==**，这部分元素 **没有 "左侧或右侧最近更小/更大" 元素**。
所以，更推荐 "**方式一**"。
> [!summary]
> 无论哪种方式：
>
> - 找 "**最近更大元素**" 都是用 **"栈底->栈顶" 递减** 的栈
> - 找 "**最近更小元素**" 都是用 "**栈底->栈顶" 递增** 的栈
>
> [!caution] 应用一个单调栈**一次遍历==无法同时得到左右两侧的最近更大/更小元素==**，除非数组中没有重复值。
>
> 在**存在重复元素**的情况下，无论采用哪种方式，**单次遍历可能使得其中一侧得到的是"==最近的相等元素=="**：
>
> 例如，**从左到右**遍历，利用单调栈**为每个 `arr[i]` 在其==入栈==时可求得其左侧最近更小元素**，而当 `arr[i]` **==出栈==**时，能够得到其 "**右侧最近的相等或更小元素**"。
>
> 要为每个元素均得到其 "左侧 & 右侧" 的最近更小/更大元素，需要两次遍历，
> 具体说明参见：[[#求左侧及右侧的最近更小/更大元素]]
### 实现方式一
![[Excalidraw-Solution/栈_1.excalidraw.svg|750]]
%%[[Excalidraw-Solution/栈_1.excalidraw.md|🖋 Edit in Excalidraw]]%%
| 求解目标 | 遍历顺序 | 栈底->栈顶单调性 |
| ----------------- | ---------- | --------- |
| **左**侧最近的**更小**元素 | 从**左**到右遍历 | 单调**递增** |
| **右**侧最近的**更小**元素 | 从**右**到左遍历 | 单调**递增** |
| **左**侧最近的**更大**元素 | 从**左**到右遍历 | 单调**递减** |
| **右**侧最近的**更大**元素 | 从**右**到左遍历 | 单调**递减** |
> [!summary] 总结
>
> **求哪一侧**的 "最近更小/更大" 元素，就**从哪一侧**开始遍历。
>
> - 要求 **==更大==** 元素，则栈底->栈顶**严格单调==递减==**；
> - 要求 **==更小==** 元素，则栈底->栈顶**严格单调==递增==**。
>
> 如果是求 "左右侧最近的 **==相等==** 或更大/更小"，
> 则**允许栈中存在相同值**，即**维持栈 "==非严格单调==" 即可**。
以找 "左侧最近更大值" 的下标为例：
```cpp
vector<int> find_left_nearest_greater_one(vector<int>& arr) {
int n = arr.size();
vector<int> left(n, -1); // 不存在时标记为-1.
stack<int> st; // 栈中保存 "已求得左侧最近更大值的元素", 栈底->栈顶递减
for (int i = 0; i < n; ++i) {
while (!st.empty() && arr[st.top()] <= arr[i]) {
st.pop();
}
left[i] = st.empty() ? -1 : st.top();
}
return left;
}
```
> [!NOTE] 如果是求 "**`x` 左右侧最近的 `x<=y` 或 `x>=y` 的元素**"，则在 `while` 循环里去掉 `==` 的判断即可——即**允许栈中存在 "值相等元素"**。
>
### 实现方式二
略。
<br><br>
## （2）同时求左侧及右侧的最近更小/更大元素
要为每个元素均得到其 **"左侧 & 右侧" 的最近更小/更大元素**，需要 **==两趟遍历==**，具体有两种实现方式：
- 方式一：**分别应用==两次==单调栈**，各自求得其中一侧的最近更小/更大元素；
- 方式二：**只应用==一次==单调栈**，**第二趟直接==反向遍历==结果数组进行修正**。 ^6ke2l5
---
以求**左侧及右侧的最近更小元素**为例，方式二如下：
> [!NOTE] 要点： 当存在多个重复值时，必然能为 "**最右一项值**" 得到 `right[i]` 代表其 "**右侧最近更小元素**"。
>
> 从右到左反向遍历，若 `right[i]` 得到的是 **"`arr[i]` 的右侧最近相等元素**" ( 即`arr[right[i]]==arr[i]`) ，
> 则**修正为** `right[i] = right[right[i]]`。
>
> ![[Excalidraw-Solution/栈.excalidraw.svg|462]]
> %% [[Excalidraw-Solution/栈.excalidraw.md|🖋 Edit in Excalidraw]] %%
>
```cpp
vector<vector<int>> find_left_and_right_nearest_smaller_one(vector<int>& arr) {
int n = arr.size();
// 记录arr[i]左侧及右侧的"最近更小元素"的下标.
// 左侧最近更小元素不存在时标记-1, 右侧最近更小元素不存在时标记n.
vector<int> left(n, -1), right(n, n);
// 1. 应用单调栈, 从左到右遍历, 栈底->栈顶递增, 求左侧最近更小元素的下标.
stack<int> st;
for (int i = 0 ; i < n; ++i) {
while (!st.empty() && arr[st.top()] >= arr[i]) {
// 出栈时可为出栈元素得到其右侧最近的"相等或更小"元素.
right[st.top()] = i;
st.pop();
}
left[i] = st.empty() ? -1 : st.top();
st.push(i);
}
// 2. 修正arr[i]右侧的最近"相等元素"为"更小元素"
for (int i = n - 2; i >= 0; --i) {
if (right[i] != n && arr[right[i]] == arr[i]) {
right[i] = right[right[i]];
}
}
vector<vector<int>> ans;
ans.push_back(std::move(left));
ans.push_back(std::move(right));
return ans;
}
```
## （3）求数组中满足 **`i < j && arr[i] < arr[j]`** 的**最远距离** `j-i`
参见 [[99-题解/leetcode/lc-962 最大宽度坡#思路三：单调栈 & 逆序遍历 ❇️|lc-962 最大宽度坡#思路三：单调栈 & 逆序遍历]]
<br><br>
# 关于栈的应用 trick
##### （1）使用哨兵
栈中**初始时**带一个**哨兵**，保持**栈始终非空**，从而统一对 "**栈顶元素**" 的处理逻辑—— **==无需判断栈空==**。
哨兵的值应当取栈中有效元素值域之外的值。例如**栈中会存放非负整数，则哨兵可以取-1**。
例如：
- 对 "栈底->栈底递增" 的单调栈，栈底哨兵可以是 `INT_MIN`（元素值域取不到`INT_MIN`的情况下）
- 对 "栈底->栈顶递减" 的单调栈，栈底哨兵可以是 `INT_MAX`（元素值域取不到`INT_MAX`的情况下）
> [!example] 应用哨兵，而统一处理逻辑的情况：
>
> - 在链表头添加 dummy 节点；
> - 在栈中放一个哨兵节点，从而无需判断栈空。
##### （2）使用数组作为栈
**`std::vector` 作为 `std::stack`，从而==可以访问栈中任意位置节点==**。
---
# 参考资料
%%
### 关于单调栈的说明
关于两种 "单调栈" 实现方式的说明[^1]
![[_attachment/00-数据结构与算法笔记/数据结构/栈.assets/IMG-栈-6C3300EAC845C31397F25329681B298B.png|667]]
单调栈的使用总结[^2]
![[_attachment/00-数据结构与算法笔记/数据结构/栈.assets/IMG-栈-B06C4FE5224F7FB0AAAC0736D7173EE5.png|645]]
%%
# Footnotes
[^1]: [【图解单调栈】两种方法，两张图秒懂！——灵茶山艾府]( https://leetcode.cn/problems/next-greater-node-in-linked-list/solutions/2217563/tu-jie-dan-diao-zhan-liang-chong-fang-fa-v9ab/ )
[^2]: [zhouzhou/数据结构/\[数据结构\]单调栈（一）：基础篇.md at main · Mrliduanyang/zhouzhou · GitHub](https://github.com/Mrliduanyang/zhouzhou/blob/main/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/%5B%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%5D%E5%8D%95%E8%B0%83%E6%A0%88%EF%BC%88%E4%B8%80%EF%BC%89%EF%BC%9A%E5%9F%BA%E7%A1%80%E7%AF%87.md)