「手撕算法」锁定大厂看这就可

假设将学生从高年级到低年级排列，随着时间的推移，高年级同学从队列头部毕业，低年级从尾部进入。大部分学校都有校队，假设小林高三，我高二，小七高一，小林毕业接班的是我，我毕业，很可能就是小七接班，而当我进队的那一刻，小七即使进的早但是战斗力没我高，所以小七是永远没计划被选中啦。所以，纵观全队，不仅有着队列的性质，也有着单调的性质，所以就是单调队列。

为什么需要单调队列

比较明显的作用是，用来维护队列处理顺序中的区间最大值。

高频面试题----滑动窗口最大值

滑动窗口没向后滑动一位，就有一个元素从队首出队，同时也会有个元素从队尾入队。这个题需要求区间的最大值：意味着需要维护在队列处理顺序中的区间最大值，直接上代码附上注释

#define MAX_N 1000 int q[MAX_N + 5], head, tail; void interval_max_number(int *a, int n, int m) {     head = tail = 0;     for (int i = 0; i < n; i++) {         // a[i] 入队，将违反单调性的从队列 q 中踢出         while (head < tail && a[q[tail - 1]] < a[i]) tail--;         q[tail++] = i; // i 入队         // 判断队列头部元素是否出了窗口范围         if (i - m == q[head]) head++;         // 输出区间内最大值         if (i + 1 >= m) {             printf("interval(%d, %d)", i - m + 1, i);             printf(" = %d ", a[q[head]]);         }     }        return ; } 

5 栈与单调栈

栈结构对应于队列，可以将栈想象为一个只有单出口的羽毛球筒，羽毛球只能从单一的入口放入和取出。假设我们将1，2,3三个球放进球桶，如果取出来此时就是3,2,1。性质就很明显了，先进后出的结构

栈结构本身维护的是一种完全包含的关系。这种包含关系在函数之间的运行体现的玲离尽致，也就是一种包含关系，如果主函数调用函数B，那么函数B一定会在主函数结束之前结束。

单调栈

此时应该了解了栈和队列，那么我问你，你觉得栈和队列最大的区别是啥?

你可能毫不犹豫的可以回答栈是先进后出，队列是先进先出。ok，那我再问你，堵住了出口的单调队列和栈有什么区别?这是不是就没什么区别了，单调队列为了维护其单调性，在入队的时候会将违反单调性的元素弹出去，这就相当于栈的同一段进出，是的，堵住出口的单调队列就是我们现在要说的单调栈，目前以单调递减栈为例

单调栈

当序列中的12号元素入栈以后，此时单调栈有4个元素，从栈底到栈顶分别为23,18,15,9，按照原始序列为2 5 9 12。此时我们关注12号元素和9号元素的关系。如果12号元素入栈，为了保证栈的单调递减性，最终放在9号上面，此时我们虽然不是第十个元素和十一号元素值多少，但是这两个元素的值一定是比9号元素小，这就是单调栈的性质。所以，单调队列是用来维护区最值的高效结构，单调栈呢是维护最近大于或小于的高效结构。下面看个例子

题目：判断括号序列是否合法

示例 合法

({})  {()} 

示例 非合法

([)] (((){}  public boolean isValid(String s) {         Stack stack = new Stack<>();         Map<Character,Character> map = new HashMap<>();         char[] chars = s.toCharArray();         map.put(')','(');         map.put('}','{');         map.put(']','[');         for(int i=0;i < s.length();i++){             if(!map.containsKey(chars[i])) {                 //为左括号时直接入栈                 stack.push(chars[i]);             }else{                 //为右括号时，如果栈为空或者栈顶与该括号类型不匹配返回false                 if(stack.empty() || map.get(chars[i]) != stack.pop()){                     return false;                 }             }         }         //字符串遍历完毕后，如果栈为空返回true，反之返回false         return stack.empty();     } 

6 递推套路

在分享递推之前，先和大家分享与之紧密的数学原理：容斥原理

（编辑：应用网_阳江站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!