利用单调队列解决区间最大（最小）值问题

部分问题需要不断获取一个滑动窗口的最大（最小）值，此时可以利用堆、二分查找等方式解决，除此之外，利用单调队列解决较为简洁且效率高。
单调队列顾名思义为队列的变种，但是单调队列除具有尾部添加、头部删去等行为外，还具有尾部删除行为（类似于出栈），单调队列中所有元素为数组中某元素的下标，而非元素的具体数值，队列中对应的数值呈单调，若要实时获取最大值，则应该采用递减单调队列，反之采用递增单调队列。

单调队列典型题目为Leetcode239题，题解如下所示：

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        decQue=[]
        res=[]
        for i in range(len(nums)):
            while len(decQue)!=0 and nums[decQue[-1]]<=nums[i]:
                decQue=decQue[:-1]
            decQue.append(i)
            while decQue[0]+k<=i:
                decQue=decQue[1:]
            if i>=k-1:
                res.append(nums[decQue[0]])
        return res

循环内代码含义：在滑动窗口获取新的元素时，从队列末尾排出所有对应元素数值小于新获得数值的下标，直到队列为空，之后再将新元素的下标填入队列末尾，从而保持队列内所有下标对应的数值呈下降趋势；在此之后，删去队列头部距离新元素超过距离的值，并判断是否要在结果中添加队列中最大值。

分析一下为什么递减单调队列要这么做：如果想获取滑动窗口内的最大值，那么队列应该尽量保存距现在最近的最大值，如果队列中某个较靠前的值相比某个靠后的值更小，那么这个值就没有必要被保存，这一部分就对应的删除队列尾部元素的操作；删除队列头部元素的操作更易理解，即排除已经不在窗口内元素。

同样适合用单调队列解决的题目：
https://leetcode-cn.com/problems/best-sightseeing-pair/