一.知识点总结

1.单调栈：是一个栈，不过栈内元素保证单调性。即，栈内元素要么从小到大，要么从大到小。 而单调栈维护的就是一个数前(后)第一个大于(小于)他的数。

单调栈的伪代码：

while(栈顶元素比入栈元素小且栈不空){
        栈顶元素弹出
}
元素入栈

首先要知道单调栈入栈的的是下标。对于入栈元素直接入栈会破坏单调性，所以需要栈顶元素出栈，后加入当前元素，使得我们当前的元素再加进去不会破坏它的单调性。

2.利用栈解决表达式求值的问题：我们要知道利用栈的先进后出的性质可以用来实现对于表达式求值，这也是栈的一个比较常见使用方式。

对于表达式求值需要引入三个有关表达式的基本概念：

对于算术表达式一般分成三种有：前缀、后缀和中缀
中缀表达式：救是我们常见的算术表达式，就是一眼看上去就能理解的表达式，例如：2*(5+8)
前缀表达式：形如"op A B"即操作数在两个运算数的前面
后缀表达式：形如"A B op"即操作数在两个运算数的后面

我们平时直观看见的就是中缀表达式，但是对于计算机而言其更容易计算的是后缀表达式的值，所以我们处理的总体思路就是：先将中缀表达式转换为 后缀表达式，然后对后缀表达式求值。

下面是实现思路：

中缀表达数转后缀表达式：
1.建立一个存储运算符的栈，对中缀表达式进行扫描。
(1)如果遇到一个数就直接存进后缀表达式中。
(2)如果遇到了一个左括号，就把左括号直接入栈。
(3)如果遇到右括号，不断取出栈顶并输出，直到栈顶为左括号，然后左括号出栈。
(4)如果遇到运算符，只需要栈顶符号的优先级补丁与新符号，就不断出栈并输出，然后将新符号入栈。
2.依次取出并存储栈中所有剩余的符号。

后缀表达式求值：
1.建立一个用于存储的数的栈，对后缀表达式进行依次扫描
(1)如果遇见一个数，那么就把这个数直接入栈
(2)如果遇到运算符，就取出栈顶的两个数进行计算，然后把结果入栈。
2.最后的栈顶元素就是表达式的值

3.链表：链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。但是广义上链表实现有很多种，不仅仅可以通过指针，还可以通过数组来实现，c++的STL中也有链表的实现，链表相比于数组，更容易进行插入删除。

下面是利用指针实现链表的插入和删除操作：

插入：//链表的插入分为头插法和尾插法 分别表示从头部插入一个元素，还是尾部插入一个元素
x= p -> next;
p -> next = q;
q -> next = x;
删除：
x = p -> next;
p -> next = x -> next;
free(x);

4.滑动窗口：简单来说就是利用双指针来维护一个窗口，思路很简单但是对于左右两个指针的细节处理很困难，下面给出滑动窗口的框架模板：

/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {
    unordered_map<char, int> need, window;
    for (char c : t) need[c]++;
    
    int left = 0, right = 0;
    int valid = 0; 
    while (right < s.size()) {
        // c 是将移入窗口的字符
        char c = s[right];
        // 右移窗口
        right++;
        // 进行窗口内数据的一系列更新
        ...

        /*** debug 输出的位置 ***/
        printf("window: [%d, %d)\n", left, right);
        /********************/
        
        // 判断左侧窗口是否要收缩
        while (window needs shrink) {
            // d 是将移出窗口的字符
            char d = s[left];
            // 左移窗口
            left++;
            // 进行窗口内数据的一系列更新
            ...
        }
    }
}

二.牛刀小试

问题1：滑动窗口的最大值

由于是要求最大值，但是由于区间长度的限制，所以我们在窗口收缩的时候不仅仅要注意最大值的维护，还要注意最大值是否在窗口中。

问题2：实现二叉树先序，中序和后序遍历

该题有点乱入，可以参考堆栈总结(一)，三种遍历方式都可以通过递归快速实现，条理清晰，代码容易实现。

问题3：表达式求值

栈最基本的实现，但是本题的细节仍然有很多需要注意的，特别是在字符串中对数字、符号的分离和栈中是否还有元素。

题目4：单调栈

题目要求做左边和右边的最小值，所以只需要进行两次遍历即可，一遍正序，一遍逆序，但是题目最后需要返回的是vecter<vecter>，所以可以提前分配空间进行存储。

alt

题目5：合并k个已排序的链表

由于是k个有序链表，合并起来只需要每次将最值取出，插入到需要返回的链表中，最后就可以返回一个有序链表了。(提示：这里面可以使用尾插法哦！)