第一章 栈和队列（2）

生成窗口最大值数组
实现一个函数，输入一个数组arr，窗口大为w。输出一个长度为n-w+1的数组res，re[i]表示每一个窗口的最大值。暴力方法的时间复杂度为O(N*w)，我们提出一个O(N)的实现。
使用双端队列qmax来实现窗口最大值的更新，qmax存放arr长得下标。遍历到arr[i]，qmax的存放规则为：
如果qmax空，直接放入i，结束；
如果不为空，取出qmax队尾的存放下标j，arr[i]>arr[j]?qmax.push_back(i):(j弹出，重复qmax的放入规则。)
qmax的弹出规则为：
如果qmax队头的下标等于i-w，说明qmax队头的下标已过期，弹出当前队头的下标。

单调栈结构
问题：给定一个不重复的数组arr，找到每一个i位置左边和右边离i位置最近且值比arr【i】小的位置。
进阶：arr可重复
以上两问题均实现O(N)的算法
下面用例子来展示单调栈的使用和求解流程,初始时arr ={3,4,1,5,6,2,7}，stack从栈顶到栈底为:{};
遍历到arr[0]==3，发现stack为空,就直接放入0位置。stack从栈顶到栈底为:{0位置(值是3)};
遍历到arr[1]==4，发现直接放入1位置,不会破坏stack从栈顶到栈底的位置所代表的值是严格递减的,那么直接放入。stack从栈顶到栈底依次为:{1位置(值是4)、0位置(值是3)};
遍历到arr[2]==1,发现直接放入2位置（值是1)，会破坏stack从栈顶到栈底的位置所代表的值是严格递减的,所以从stack开始弹出位置。如果×位置被弹出,在栈中位于×位置下面的位置,就是×位置左边离×位置最近且值比arr[x]小的位置;
当前遍历到的位置就是×位置右边离×位置最近且值比arr[x]小的位置。从 stack 弹出位置1,在栈中位于1位置下面的是位置0,当前遍历到的是位置2，所ans[1]=10,2]。弹出1位置之后，发现放入2位置（值是1）还会破坏stack从栈顶到栈底的位置所代表的值是严格递减的，所以继续弹出位置0。在栈中位于位置值,当前遍历到的是位置2，所下面已经没有位置了，说明在位置0左边不存在比 arr[0]小的以 ans[0]=1-1,2}。stack已经为空,所以放入2位置（值是1），stack从栈顶到栈底为:{2位置(值是1)};
遍历到arr[3]==5，发现直接放入3位置，不会破坏stack 从栈顶到栈底的位置所代表的值是严格递减的，那么直接放入。stack从栈顶到栈底依次为:{3位置(值是
5)、2位置(值是1)};
遍历到arr[4]==6，发现直接放入4位置，不会破坏stack从栈顶到栈底的位置所代表的值是严格递减的，那么直接放入。stack从栈顶到栈底依次为:{4位置(值
是6)、3位置(值是5)、2位置(值是1)};
遍历到 arr[5]==2，发现直接放入5位置，会破坏stack 从栈顶到栈底的位置所代表的值是严前是位置(5，ans[4]={3,5}。
格递减的，所以开始弹出位置。弹出位置4,栈中它的下面是位置3，当后放入5位置就不会破坏弹出位置3，栈中它的下面是位置2，当前是位置5，ans[3]={2,5}。然
stack的单调性了。stack从栈顶到栈底依次为:{5位置(值是2)、2位置(值是1)};栈底的位置所代表的值是遍历到arr[6]==7，发现直接放入6位置，不会破坏stack从栈顶到
严格递减的,那么直接放入。stack从栈顶到栈底依次为:{6位置(值是7)、5位置(值是2)、2位置(值是1)}。
遍历阶段结束后,清算栈中剩下的位置。
弹出6位置,栈中它的下面是位置5,6位置是清算阶段弹出的,所以ans[5]={2,-1};
弹出5位置,栈中它的下面是位置2，5位置是清算阶段弹出的,所以ans[5]={2,-1};
弹出2位置，栈中它的下面没有位置了，2位置是清算阶段弹出的，所以 ans[2]={-1,-1}.

可重复时
如果重复的两个位置之间的元素都大于这两个位置的值，则两个位置在栈中可以合并。核心思想就是这个。