单调栈使用总结

其实这些总结大部分写给我自己看，所以我也不打算写的很详细，只想记一些比较重要得多感触和体会，其余就随意希望节约点时间。

关于单调栈的定义以及基本使用可以参考这篇文章：

​​​​​​单调栈_ZHE-CSDN博客

单调栈使用模板

stack sta;
vector vec; //假设已经初始化，有了一些元素
for(auto i : vec) {
    while(!sta.empty() && i > sta.top()) {
        sta.pop()
        //do something
    }
    sta.push(i);
}

单调栈什么时候使用呢？

1. 对于数组中的元素，我们需要比较其大小，但是元素之间的比较具备不确定性以及延迟性。

 何谓不确定性？

        假设我们遍历数组过程中发现元素a后，与a进行比较的时刻是不确定的，换句话说，不确定是否存在a之后的元素b会与a进行比较

 何谓延迟性？

        和不确定性有点类似，也就是说比较不一定会发生在发现当前元素的紧接下来的时刻，而是发生在以后的某个不确定的时刻，甚至可能不会发生

2. 我们希望线性事件解决问题，通常方式是遍历数组

3. 我们希望保存一定的状态，并且这样的状态能够用数组内元素大小关系来记录。

4. 如果我们解决了部分问题后，对于后续问题是不影响的。也就是说如果前面问题尚未解决的话会影响后面的问题，这体现为延迟性。但是如果前面部分问题解决了是不影响后面问题的解决，这表示一定程度上的状态无关性。

说的很抽象，找了两三道比较好的题。之前的引用链接里用了个接雨水的题目，我感觉其实对于初学者，这道题用单调栈并不显然。可以先看看这两题：

​​​​​​力扣

力扣

最后再回过头来看看节雨水这个题目。

我们为什么可以想到使用单调栈呢，因为它具备这样使用的特征：

1. 接雨水的充要条件是形成凹槽，形成凹槽的表现形式表现为两高中低，可以通过数字大小的比较关系来保存这样的状态。

2. 我们希望能够扫描数组得到答案。

3.扫描数组从左到右的过程中，我们并不清楚右边界在什么时候形成，以及是否会形成，这也就是上述说的不确定性和延迟性。

4. 如果我们把整个图分为两个部分，左右两边各形成一个凹槽，那么我们从左到右遍历数组的过程中，解决了左边凹槽接雨水的问题后是不会影响右边的。