单调栈\单调队列

偶然想起单调栈和单调队列的知识点，就想把它记录下来

单调栈和单调队列都是维护一个容器内元素的单调性/滑窗是单调队列的推广这里不细说了，会滑窗一定会单调队列

单调栈可以获取从当前元素起，左边第一个比自己大的元素或者比自己小的元素，右边对称同理。来看一道最长子序列上升的题。

 1 class Solution {
 2 public:
 3     int lengthOfLIS(vector<int>& nums) {
 4         int n=nums.size(),top=0;
 5         int st[n+1];
 6         for(int i=0;i)
 7         {
 8             if(!top||st[top-1]nums[i];
 9             else
10             {
11                 int t=lower_bound(st,st+top,nums[i])-st;
12                 st[t]=nums[i];
13             }
14         }
15         return top;
16     }
17 };

对于当前元素和栈顶元素比较，如果当前元素大于栈顶元素，压栈更新最长子序列

如果小于等于栈顶元素，我们可以从栈里找第一个>=当前元素的元素a[i]，把它替换

替换后i之前的所有子序列长度不会改变，而对于与替换的a[j]来说，以a[j]结尾的最长子序列和以a[i]的相同，而且对于未来的元素,a[i]比a[j]小

所以a[i]更优。即如果未来需要从a[j]结尾的长度更新，那么a[i]是较优的，基于这种替换规则我们能证明算法的正确性；