首页 > 试题广场 >

滑动窗口的最大值

[编程题]滑动窗口的最大值
  • 热度指数:578534 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个长度为 n 的数组 num 和滑动窗口的大小 size ,找出所有滑动窗口里数值的最大值。

例如,如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3,那么一共存在6个滑动窗口,他们的最大值分别为{4,4,6,6,6,5}; 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个: {[2,3,4],2,6,2,5,1}, {2,[3,4,2],6,2,5,1}, {2,3,[4,2,6],2,5,1}, {2,3,4,[2,6,2],5,1}, {2,3,4,2,[6,2,5],1}, {2,3,4,2,6,[2,5,1]}。

窗口大于数组长度或窗口长度为0的时候,返回空。

数据范围: ,数组中每个元素的值满足 
要求:空间复杂度 ,时间复杂度


示例1

输入

[2,3,4,2,6,2,5,1],3

输出

[4,4,6,6,6,5]
示例2

输入

[9,10,9,-7,-3,8,2,-6],5

输出

[10,10,9,8]
示例3

输入

[1,2,3,4],5

输出

[]
import java.util.ArrayList;

public class Solution {
public static ArrayList<Integer> maxInWindows(int [] num, int size)
    {
        if (size == 0) {
            return new ArrayList<>();
        }
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0;i < num.length && i <= num.length - size;i ++) {
            int max = Integer.MIN_VALUE;
            for (int j = 0;j < size;j ++) {
                max = Math.max(max, num[i + j]);
            }
            list.add(max);
        }
        return list;
    }
}

发表于 2018-06-26 17:21:23 回复(1)
更多回答
推荐
import java.util.*;
/**
用一个双端队列,队列第一个位置保存当前窗口的最大值,当窗口滑动一次
1.判断当前最大值是否过期
2.新增加的值从队尾开始比较,把所有比他小的值丢掉
*/
public class Solution {
   public ArrayList<Integer> maxInWindows(int [] num, int size)
    {
        ArrayList<Integer> res = new ArrayList<>();
       	if(size == 0) return res;
		int begin;	
		ArrayDeque<Integer> q = new ArrayDeque<>();
		for(int i = 0; i < num.length; i++){
			begin = i - size + 1;
			if(q.isEmpty())
				q.add(i);
			else if(begin > q.peekFirst())
                q.pollFirst();
		
			while((!q.isEmpty()) && num[q.peekLast()] <= num[i])
                q.pollLast();
			q.add(i);	
			if(begin >= 0)
				res.add(num[q.peekFirst()]);
		}
		return res;
    }
}

编辑于 2015-09-02 14:11:26 回复(51)

剑指Offer-滑动窗口的最大值

package StackAndQueue;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.PriorityQueue;
/**
 * 滑动窗口的最大值
 * 给定一个数组和滑动窗口的大小,找出所有滑动窗口里数值的最大值。例如,如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3,那么一共存在6个滑动窗口,他们的最大值分别为{4,4,6,6,6,5}; 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个: {[2,3,4],2,6,2,5,1}, {2,[3,4,2],6,2,5,1}, {2,3,[4,2,6],2,5,1}, {2,3,4,[2,6,2],5,1}, {2,3,4,2,[6,2,5],1}, {2,3,4,2,6,[2,5,1]}。
 */
public class Solution52 {
    public static void main(String[] args) {
        Solution52 solution52 = new Solution52();
        int[] num = {2, 3, 4, 2, 6, 2, 5, 1};
        int size = 3;
        ArrayList list = solution52.maxInWindows(num, size);
        System.out.println(list);
    }
    /**
     * 最大堆方法
     * 构建一个窗口size大小的最大堆,每次从堆中取出窗口的最大值,随着窗口往右滑动,需要将堆中不属于窗口的堆顶元素删除。
     *
     * [@param num
     * @param size
     * @return](/profile/547241) */
    public ArrayList maxInWindows_2(int[] num, int size) {
        ArrayList res = new ArrayList();
        if (size > num.length || size < 1) return res;
        // 构建最大堆,即堆顶元素是堆的最大值。
        PriorityQueue heap = new PriorityQueue((o1, o2) -> o2 - o1);
        for (int i = 0; i < size; i++) heap.add(num[i]);
        res.add(heap.peek());
        for (int i = 1; i + size - 1 < num.length; i++) {
            heap.remove(num[i - 1]);
            heap.add(num[i + size - 1]);
            res.add(heap.peek());
        }
        return res;
    }
    /**
     * 双队列方法
     * 滑动窗口的最大值总是保存在队列首部,队列里面的数据总是从大到小排列。
     *
     * [@param num
     * @param size
     * @return](/profile/547241) */
    public ArrayList maxInWindows(int[] num, int size) {
        ArrayList res = new ArrayList();
        if (num == null || num.length == 0 || size == 0 || size > num.length) {
            return res;
        }
        Deque deque = new LinkedList();
        for (int i = 0; i < num.length; i++) {
            if (!deque.isEmpty()) {
                // 如果队列头元素不在滑动窗口中了,就删除头元素
                if (i >= deque.peek() + size) {
                    deque.pop();
                }
                // 如果当前数字大于队列尾,则删除队列尾,直到当前数字小于等于队列尾,或者队列空
                while (!deque.isEmpty() && num[i] >= num[deque.getLast()]) {
                    deque.removeLast();
                }
            }
            deque.offer(i); // 入队列
            // 滑动窗口经过一个滑动窗口的大小,就获取当前的最大值,也就是队列的头元素
            if (i + 1 >= size) {
                res.add(num[deque.peek()]);
            }
        }
        return res;
    }
}
编辑于 2018-04-19 12:56:37 回复(4)
class Solution {
public:
    //只考虑两端增删变化的影响
    int MaxinW(const vector& num, int low, int high)
    {
        int MaxVal = INT_MIN;
        for (int j = low; j <= high; j++)
            MaxVal = max(num[j], MaxVal);
        return MaxVal;
    }
    vector maxInWindows(const vector& num, unsigned int size)
    {
        vectorres;
        int len=num.size();
        if (len len)return res;
        int MaxVal = MaxinW(num, 0, size - 1); res.push_back(MaxVal);
        for (int low = 1, high = size; high < len; low++,high++)
        {
            if (num[high] >= MaxVal)
                MaxVal = num[high];
            if (num[low - 1] == MaxVal)
                MaxVal = MaxinW(num, low, high);
            res.push_back(MaxVal);
        }
        return res;
    }
};

2.参考牛友

class Solution {
public:
    //双端队列
    //时间复杂度o(n),空间复杂度为o(n)
    //deque s中存储的是num的下标
    vector<int> maxInWindows(const vector<int>& num, unsigned int size)
    {
        vector<int>res;
        deque<int>s;
        int len=num.size();
        if (len <= 0||size<=0||size>len)return res;         
        for (int i = 0;i < len; i++)
        {
            while (!s.empty() && num[s.back()] <= num[i])//当前值比队列从后往前的大,成为下一个待选值
                s.pop_back();
            while (!s.empty()&&i - s.front() + 1>size)//最大值已不在窗口中
                s.pop_front();
            s.push_back(i);

            if (i + 1 >= size)//当滑动窗口首地址i大于等于size时才开始写入窗口最大值
             res.push_back(num[s.front()]);
        }
        return res;
    }

};
编辑于 2018-12-10 16:29:50 回复(1)

python O(n) solution

# -*- coding:utf-8 -*-
class Solution:
    def maxInWindows(self, nums, k):
        # write code here
        if not k or k>len(nums):return []

        cur_max = max(nums[:k])
        max_nums = [cur_max]
        for i in range(0, len(nums) - k):
            if nums[i] == cur_max:
                cur_max = max(nums[i + 1:i + k + 1])
            elif nums[i + k] > cur_max:
                cur_max = nums[i + k]
            max_nums.append(cur_max)
        return max_nums
编辑于 2017-10-14 08:07:13 回复(6)

双端队列,两端删除添加可用数组模拟。
push/pop操作最后
unshift/shift操作最前

function maxInWindows(num, size)
{
  // 双端队列(两端都可以实现插入和删除)
  // 队列首位永远是最大值
  // 每次进来一个数,依次和前面的数比较,如果进来的数大,则前面的数直接弹出(在后面不可能最大)
  // 如果进来的数小,则比较下标,下标不存在的将其删除

  // 数组实现双端队列,arr存的是下标,arr[0]存最大值下标
  var arr = [];
  // 结果数组
  var res = [];

  if (size === 0) {
    return res;
  }

  for (var i = 0; i < num.length; i++) {
    // 从第一个开始循环(可以理解成滑动窗口右侧从第一个移动到最后一个)
    // 进来一个数,依次从最后一个数开始比较
    while (arr.length > 0 && num[i] > num[arr[arr.length-1]]) {
      // 如果进来的数比最后一个大,则将最后一个踢出去,pop
      arr.pop();
    }
    arr.push(i);

    // 再判断前面的数是否超了,由于每次进来的数如果更大,则将前面的踢出去,导致arr[0]的下标永远在最前面
    if (i - arr[0] + 1 > size) {
      arr.shift();
    }
    if (i >= size - 1) {
      res.push(num[arr[0]]);
    }
  }
  return res;
}

var res = maxInWindows([2,3,4,2,6,2,5,1], 3);
console.log(res);
发表于 2019-08-08 21:10:29 回复(0)
function maxInWindows(num, size)
{
    // write code here
    if(!num){
        return null;
    }
    var len = num.length;
    var arr = [];
    if(size > len || size <= 0){
        return arr;
    }
    if(size == 1){
        return num;
    }
    if(size == len){
        //注意这里用Math.max()的时候,如果直接传的是数组名,要在前面加...符号,不然不成功
        arr.push(Math.max(...num));
        return arr;
    }
    for(var i = 0;i < len - size + 1;i++){
        var num1 = [];
        num1 = num.slice(i,i+size);
        arr.push(Math.max(...num1));
    }
    return arr;
}
if好像写的有点多~

发表于 2021-03-23 16:48:24 回复(0)
# -*- coding:utf-8 -*-
class Solution:
    def maxInWindows(self, num, size):
        #双端队列维护从大到小元素的索引
        #步骤
        #每遇到一个元素,从后往前将队列中小于该元素的索引全部弹出
        #(因为在滑动窗口长度内,小于该元素的值不可能成为最大值,1是该元素在他们后面,2是该元素值比他们大)
        if size>len(num) or size<1:
            return []
        from collections import deque
        queue = deque()
        res = [] 
        for index,val in enumerate(num):
            #队列为空时加入第一个元素
            if index==0:
                queue.append(index)
            else:
                #判断队首是否滑出了窗口
                if index-queue[0]==size:
                    queue.popleft()
                #为当前元素在队列中找到相应位置,其后所有元素弹出
                while queue and num[index]>=num[queue[-1]]:
                    queue.pop()
                queue.append(index)
                print(queue)
            #当滑动窗口大小==size时,可以开始记录最大值
            if index>=size-1:
                res.append(num[queue[0]])
        return res 

发表于 2019-11-21 11:08:19 回复(0)
/*
表达不清楚的地方,请各位批评指正!
这道题可以用双向队列解决(就是头尾都可以push,pop的队列)
时间复杂度 O(N)
方法如下几点:
    1.当我们遇到新数时候,将新的数和双向队列的末尾比较,
       若果末尾比新数小,则把末尾pop_back,
       直到末尾比新数大或者队列为空才停止;
     2.这样就保证队列元素是从头到尾降序的,
         由于队列里只有窗口内的数,所以它们其实是窗口内
         第一大,第二大…的数。
     3.保持队列里只有窗口大小的数的方法是,
         右边进一个,左边出一个。
     4.由于队列加新数时,已经删除了部分没用的数,
        所以队列头的数并不一定是窗口最左的数,
        这里有个小技巧,就是队列中存原数组的下标,
        这样既可以得到这个数,也可以判断是否是窗口
        左边的数了。
*/
class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size)
    {
        vector<int> ret;
        if(num.empty() || size == 0)
            return ret;
        deque<int> deq;
        for(unsigned int i = 0;i < num.size(); ++i){
            //每当新数进来时,如果队列头部的下标是窗口最左边的下标,则删除队列头
            if(!deq.empty() && deq.front() < i - size)
                deq.pop_front();
            //队列中加入新数
            deq.push_back(i);
            //队列头部就是该窗口最大的!
            if((i + 1) >= size)
                ret.push_back(num[deq.front()]);
        }
        return ret;
    }
};

编辑于 2016-09-02 21:16:31 回复(3)
int maxValue(int arr[], int begin, int window){
 int max = INT_MIN;
 int end = begin + window;
 for(int i = begin; i < end; i++){
 if(max < arr[i]){
 max = arr[i];
 }
 }
 return max;
}
vector<int> windowValue(int arr[], int n, int window){
 vector<int> result;
 int end = n - window + 1;
 for(int i=0; i < end; i++){
 result.push_back(maxValue(arr, i, window));
 }
 return result;
}

编辑于 2015-04-11 15:11:19 回复(0)
import java.util.*;

public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size)
    {
        if(num == null || size == 0 || size > num.length) {
            return new ArrayList<Integer>();
        }
        int windowNum = num.length - size + 1;
        LinkedList<Integer> list = new LinkedList<>();
        ArrayList<Integer> res = new ArrayList<>();
        int maxTmp = Integer.MIN_VALUE;
        for(int i = 0; i < windowNum; i++) {
            maxTmp = num[i];
            for (int j = 1; j < size; j++) {
                maxTmp = num[i+j] > maxTmp ? num[i+j] : maxTmp;
            }
            res.add(maxTmp);
        }
        return res;
    }
}

发表于 2018-08-14 15:37:02 回复(1)
#python2.7 O(n) 时间24ms 内存5760k
class Solution:
    def maxInWindows(self, num, size):
        # write code here
        length = len(num)
        if size<=0 or size>length:return []
        i = 0
        ans =[max(num[:size])]
        while size+i < length:
            if num[i]<ans[-1]:
                ans.append(max([ans[-1],num[i+size]]))
            else:
                ans.append(max(num[i+1:i+size+1]))
            i+=1
        return ans

发表于 2017-12-08 10:35:35 回复(1)
public ArrayList<Integer> maxInWindows(int[] num, int size) {
		ArrayList<Integer> maxWindows = new ArrayList<>();
		// 特殊情况处理
		if (num.length == 0 || num == null || num.length < size) {
			return maxWindows;
		}

		if (num.length >= size && size >= 1) {
			// 用来保存可能是滑动窗口最大值的数字的下标
			ArrayDeque<Integer> indexDeque = new ArrayDeque<>();

			for (int i = 0; i < size; i++) {
				// 如果已有数字小于待存入的数据,
				// 这些数字已经不可能是滑动窗口的最大值
				// 因此它们将会依次地从队尾删除
				while (!indexDeque.isEmpty() && num[i] >= num[indexDeque.getLast()]) {
					indexDeque.pollLast();
				}

				indexDeque.addLast(i);
			}

			for (int i = size; i < num.length; i++) {
				maxWindows.add(num[indexDeque.getFirst()]);
				// 如果已有数字小于待存入的数据,
				// 这些数字已经不可能是滑动窗口的最大值
				// 因此它们将会依次地从队尾删除
				while (!indexDeque.isEmpty() && num[i] >= num[indexDeque.getLast()]) {
					indexDeque.pollLast();
				}
				// 如果队列的头部元素已经从滑动窗口里滑出,滑出的数字需要从队列的头部删除
				if (!indexDeque.isEmpty() && indexDeque.getFirst() <= (i - size)) {
					indexDeque.pollFirst();
				}

				indexDeque.addLast(i);
			}
			maxWindows.add(num[indexDeque.getFirst()]);
		}
		return maxWindows;

	}

发表于 2016-05-27 21:46:16 回复(0)
import java.util.ArrayList;
import java.util.Arrays;

public class Solution {
    ArrayList<Integer> maxInWindows(int [] num, int size)
    {
            int[] m_Seq=new int[size];

             ArrayList m_MaxSet=new ArrayList(); 
        
            if (num.length < size) return m_MaxSet;
        
            if (size==0) return m_MaxSet;

            for(int i=0;i<=num.length-size;i++){

                m_Seq = Arrays.copyOfRange(num,i,i+size);

                Arrays.sort(m_Seq);

                m_MaxSet.add(m_Seq[m_Seq.length-1]);

            }
        
            return m_MaxSet;
    }
}

发表于 2015-04-18 00:28:20 回复(0)
import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        ArrayList<Integer> list=new ArrayList<Integer>();//用来放每个滑窗的max
        if(num.length==0||size==0){return list;}
        for(int i=0;i<=num.length-size;i++){
            int[] arr=new int[size];
            int j=0,k=i;
            while(j<=size-1){
                arr[j++]=num[k++];
            }
            list.add(Max(arr));
        }
        return list;
    }
    public int Max(int[] array){
        int max=array[0];
        for(int i=0;i<=array.length-1;i++){
            if(array[i]>max){
                max=array[i];
            }
        }
        return max;
    }
}

发表于 2022-07-30 14:15:50 回复(0)

双端队列
时间复杂度:O(n) 空间复杂度:O(k) k为窗口大小

class Solution:
    def maxInWindows(self , num: List[int], size: int) -> List[int]:
        res = []
        dq = []
        for i in range(len(num)):
            while dq and num[dq[-1]] < num[i]:
                dq.pop()
            dq.append(i)
            if i - dq[0] >= size:
                dq.pop(0)
            if i + 1 >= size:
                res.append(num[dq[0]])
        return res
发表于 2022-05-17 20:16:42 回复(0)
 public List<int> maxInWindows (List<int> num, int size) {
         if (size <= 1 || num.Count == 0)
                return num;
            LinkedList<int> list = new LinkedList<int>();
            List<int> res = new List<int>();
            for (int i = 0; i < num.Count; i++)
            {
                while (list.Count != 0 && num[i] > num[list.Last.Value])
                {
                    list.RemoveLast();
                } //直到当前元素比队列元素小或队列中无元素
                list.AddLast(i);
                if (list.First.Value + size == i)
                {
                    list.RemoveFirst();
                } //考虑上一个窗口的最大值正好是上一个窗口的第一个元素的情况
                if (i + 1 >= size)
                {
                    res.Add(num[list.First.Value]);
                } //至少要等第一个窗口判断结束,将队列中窗口最大值在队列队首

            }
            return res;
}
发表于 2022-04-20 17:25:53 回复(0)
function maxInWindows(num, size)
{
    if(num.length<size||size===0) return []
    
    //第一个最大的
    let max=Math.max(...num.slice(0,size))
    let maxlist=[max]
    for(let i=size;i<num.length;i++){ 
        //大于最大值就记录
        if(num[i]>max){
            max=num[i] 
        }
        //左边界是最大就重新计算最大值
        else if(max==num[i-size]) max=Math.max(...num.slice(i-size+1,i+1))
        maxlist.push(max)
    }
    return maxlist
}


发表于 2022-03-23 12:05:33 回复(1)
class Solution:
    def maxInWindows(self , num: List[int], size: int) -> List[int]:
        # write code here
        # 不满足条件时为空
        if size==0&nbs***bsp;len(num)<size:
            return []
        # 可以生成的组数
        groups=len(num)+1-size
        res=[]
        for i in range(groups):
            # i:size+i保证每次取size个大小
            res.append(max(num[i:size+i]))
        return res

发表于 2022-03-14 10:41:41 回复(0)
class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size) {
        vector<int> vec;
        for(int i=0;i+size-1<num.size();i++){
            int x = num[i];
            for(int j=i;j<=i+size-1;j++){
                x = max(num[j],x);
            }
            vec.push_back(x);
        }
        return vec;
    }
};

发表于 2022-03-03 16:24:43 回复(0)
import java.util.*;
/**
用一个双端队列,队列第一个位置保存当前窗口的最大值,当窗口滑动一次
1.判断当前最大值是否过期
2.新增加的值从队尾开始比较,把所有比他小的值丢掉
*/
public class Solution {
   public ArrayList<Integer> maxInWindows(int [] num, int size)
    {
        ArrayList<Integer> res = new ArrayList<>();
           if(size == 0) return res;
        int begin;    
        ArrayDeque<Integer> q = new ArrayDeque<>();
        for(int i = 0; i < num.length; i++){
            begin = i - size + 1;
            if(q.isEmpty())
                q.add(i);
            else if(begin > q.peekFirst())
                q.pollFirst();
        
            while((!q.isEmpty()) && num[q.peekLast()] <= num[i])
                q.pollLast();
            q.add(i);    
            if(begin >= 0)
                res.add(num[q.peekFirst()]);
        }
        return res;
    }
}
import java.util.*;
/**
用一个双端队列,队列第一个位置保存当前窗口的最大值,当窗口滑动一次
1.判断当前最大值是否过期
2.新增加的值从队尾开始比较,把所有比他小的值丢掉
*/
public class Solution {
   public ArrayList<Integer> maxInWindows(int [] num, int size)
    {
        ArrayList<Integer> res = new ArrayList<>();
           if(size == 0) return res;
        int begin;    
        ArrayDeque<Integer> q = new ArrayDeque<>();
        for(int i = 0; i < num.length; i++){
            begin = i - size + 1;
            if(q.isEmpty())
                q.add(i);
            else if(begin > q.peekFirst())
                q.pollFirst();
        
            while((!q.isEmpty()) && num[q.peekLast()] <= num[i])
                q.pollLast();
            q.add(i);    
            if(begin >= 0)
                res.add(num[q.peekFirst()]);
        }
        return res;
    }
}
发表于 2022-02-10 16:00:19 回复(0)
做了3种方法:
解法1:暴力,每次都把窗口排一遍序
import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows(int[] num, int size) {
        
        ArrayList<Integer> ret = new ArrayList<Integer>();
        
        if( size == 0 || size > num.length){
            return ret;
        }
            
        // 暴力解:直接算
        
        for(int i=0; i< num.length-size+1;i++){
            int window[] = Arrays.copyOfRange(num,i,i+size);
            Arrays.sort(window);
            ret.add(window[size-1]);
        }
        return ret;
    }
}
解法2:利用大根堆,每次取最大的元素即可
import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows(int[] num, int size) {
        // 解法2: 大根堆维护栈顶最大
        ArrayList<Integer> ret = new ArrayList<Integer>();
        // 边界
        if( size == 0 || size > num.length){
            return ret;
        }
        // 定义大根堆代表滑动窗口
        PriorityQueue<Integer> bHeap = new PriorityQueue<Integer>((o1,o2) -> o2-o1);
        // 大根堆初始化,长度为size-1
        for(int i = 0; i<size-1; i++){
            bHeap.offer(num[i]);
        }
        // 逐个窗口遍历
        for(int i=0; i< num.length-size+1;i++){
            // 先将当前区间最后一个入队,补足堆长度
            bHeap.offer(num[i+size-1]);
            // 取区间段最大值
            ret.add(bHeap.peek());
            // 区间首个元素出队,保证堆的长度永远缺1
            bHeap.remove(num[i]);
        }
        return ret;
    }
}
解法3:单调队列(大根堆自己的时间复杂度是O(nlogn),如果我们让取元素的复杂度变为O(1)呢?)
import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        // 解法3:单调队列(一个非严格递减的队列,想办法保证队首是整个队列的最大值,这样每次取最大值的时间复杂度就是O(1))

        // 定义返回
        ArrayList<Integer> arr = new ArrayList<>();
        // 边界值
        if( size==0 || size > num.length){
            return arr;
        }
        // 单调队列需要deque实现
        Deque<Integer> deque = new LinkedList<>();
        
        // 分为2段解决,一段是窗口用于初始化窗口,一段正式计算
        // 第一段,初始化窗口(只需要考虑队尾加元素)
        for(int i=0;i<size;i++){
            // 如果新入队的元素大于队尾元素,就删掉队尾,如此迭代,直到找到一个队尾>=新元素,或者到最后都没找到,也就是队列为空
            while(!deque.isEmpty() && deque.getLast()<num[i]){
                deque.removeLast();
            }
            // 循环结束后,新元素会插到一个不比它小的元素后面(或者直接成为队首),以此规律维护单调队列的递减性
            deque.addLast(num[i]);
        }
        // 第二段,窗口已经生成,开始迭代。每次都将当前单调队列队首加入返回list,并为右移窗口为下轮迭代准备
        for(int i=0;i<num.length-size+1;i++){
            // 单调队列队首元素就是当前窗口最大值
            arr.add(deque.getFirst());
            // 取完元素,单调队列开始右移,为下次做准备,如果下个窗口的屁股即将溢出,break
            if(i+size==num.length){
                break;
            }
            // 如果单调队列当前队首==当前元素(也就是窗口最左边的元素),说明最大元素在下一轮会移出窗口,单调队列也需要删除它
            if(deque.getFirst()==num[i]){
                deque.removeFirst();
            }
            // 然后准备迎接新元素,和第一段剩下的一样
            while(!deque.isEmpty() && deque.getLast()<num[i+size]){
                deque.removeLast();
            }
            // 循环结束后,新元素会插到一个不比它小的元素后面(或者直接成为队首),以此规律维护单调队列的递减性
            deque.addLast(num[i+size]);
        }
        
        return arr;
    }
}


发表于 2022-01-15 23:19:37 回复(0)