本文共 1215 字，大约阅读时间需要 4 分钟。

单调队列

解决该类问题的重点维护一个队列，从队首到队尾是递减的，队首是最大的。队尾是最小的。

队尾接受值，队首排出值。

Java实现用双端队列，前面接收值，后面排出来值。

这类题目往往是跟滑动窗口一起出现的，在滑动窗口K的范围内查找最大最小值。

1.Leetcode239 滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3

[1 3 -1] -3 5 3 6 7 3

求滑动窗口中的最大值，存储索引

class Solution {
       public int[] maxSlidingWindow(int[] nums, int k) {
           // 用双端队列实现一个单调队列        Deque
   
     queue = new LinkedList<>();        // 队首最大值中的下标索引        // 滑动窗口的思路        int n = nums.length;        int[] res = new int[n-k+1];        for(int i=0;i
    
     nums[queue.getLast()]){
                   // 队尾的其其小，排出来                queue.pollLast();            }            // 入队列            queue.offerLast(i);            // 需要判断队列中的队首是否还在滑动窗口有效范围内            if(queue.peekFirst()+k<=i){
                   //不在有效范围内了 最大值排出来                queue.pollFirst();            }            // 滑窗中最大值记录从下标2开始            if(i+1>=k){
                   res[i+1-k] = nums[queue.peekFirst()];            }        }        return res;    }}
    
   

转载地址：http://wjwdf.baihongyu.com/