单调队列和单调栈详解 - 小楼吹彻玉笙寒

单调队列和单调栈详解 - 小楼吹彻玉笙寒

单调队列和单调栈的相同点

• 单调队列和单调栈的"头部"都是最先添加的元素，"尾部"都是最后添加的元素。
• 递增和递减的判断依据是：从栈底（队尾）到栈顶（队首），元素大小的变化情况。所以队列和栈是相反的。
• 它们的操作是非常相似的。当队列长度为无穷大时，递增的单调队列和递减的单调栈，排列是一样的！
  原因在于，长度为无穷大的的队列不会在"头部"有popfront操作，而在"尾部"的操作是一模一样的：数据都从"尾部"进入，并按照相同的规则进行比较。
• 两者维护的时间复杂度都是O(n)，因为每个元素都只操作一次。

区别

• 队列可以从队列头弹出元素，可以方便地根据入队的时间顺序（访问的顺序）删除元素。
• 这样导致了单调队列和单调栈维护的区间不同。当访问到第i个元素时，单调栈维护的区间为[0, i)，而单调队列维护的区间为(lastpop, i)
• 单调队列可以访问"头部"和"尾部"，而单调栈只能访问栈顶（也就是"尾部"）。这导致单调栈无法获取[0, i)的区间最大值/最小值。

综上所述，单调队列实际上是单调栈的的升级版。单调栈只支持访问尾部，而单调队列两端都可以。当然，单调栈的编程上（两个函数）比单调队列（三个函数）要简单。

Read full article from 单调队列和单调栈详解 - 小楼吹彻玉笙寒