单调队列和单调栈

这俩东西好像差不多，放一起总结吧。

单调栈：

a0,a1,a2,a3,a4...ax...an

求ax左边第一个大于ax的元素

取 ai，aj （i<j），满足ai<aj：则对于ax（x>j），ai一定不是ax左边第一个大于ax的元素。

————————

单调队列：

a0,a1,a2,a3,a4...ax...an

取窗口长度k，{a0~ak-1}，求窗口里最大的元素。窗口每次向右滑动一格

取 ai，aj （i<j），满足ai<aj，且ij都在窗口内，则ai一定不会是本窗口以及往后的任何窗口的解。ai弹出。到此为止是单调栈的部分】

窗口往后滑一格，队列头部元素如果在窗口外，弹出（单调队列与stack的区别）

——————————————————————

换成算法大概就是

for ai{

    //ai是新iterate到的元素

    ai可能是窗口的解也可能不是，这要根据a[i+k]来判断，其中k>0

    但可以根据ai判断aj，j<i

    综上，如果ai符合要求或者比aj更具有某种特点，【并且ai比aj距离目标的物理距离更近（比如在窗口内更靠后的位置，或者距离要对比的ax更近）】，则aj就要被pop掉

}