队列结构练习题

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

• BM45 滑动窗口的最大值
• 方法一
• • • 1.Java代码
    • 2.算法分析
• 方法二
• • • 1.双向队列
    • 2、Java代码
    • 3、算法分析

题目描述

给定一个长度为 n 的数组 nums 和滑动窗口的大小 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]}。

数据范围： 1 le size le n le 100001≤size≤n≤10000，数组中每个元素的值满足 |val| le 10000∣val∣≤10000
要求：空间复杂度 O(n)，时间复杂度 O(n)

求各个滑动窗口的最大值，我首先想到的一种简单直观的方法就是逐一求取每个滑动窗口的最大值，即将每次移动后的窗口当作全新的数据段，逐一比较段内各元素的值来找出最大值

import java.util.*;
public class Solution {
    public ArrayList maxInWindows(int [] num, int size) {
        if(num==null || num.length==0){
            return null;
        }
        
        ArrayList max_nums = new ArrayList();
        int window_begin = 0;
		
		//逐一检查所有滑动窗口
        while(window_begin+size<=num.length){
            int max = num[window_begin];
            int window_num_cur = window_begin;
            //获取每个滑动窗口内的最大元素
            while(window_num_cur
                if(max
                    max = num[window_num_cur];
                }
                window_num_cur++;
            }
            max_nums.add(max);
            window_begin++;
        }
        return max_nums;
    }
}

以上代码简单易懂，易于实现，但缺点是时间复杂度较大，达到O(nm)，属于暴力破解，一旦数据队列和滑动窗口大小扩大，算法效率低下的劣势将暴露无遗。

尝试基于滑动窗口构造一个初始有序的线性结构，且每次滑动需要将左侧元素移出窗口，右侧元素移入窗口，且移入之前需设法在右端进行操作使得该线性结构保持有序，以便快速获取当前窗口最大值，故可使用双向队列满足这一需求。

Java类库已经提供双向队列结构ArrayDeque供我们直接使用，现基于ArrayDeque构造一个有序队列，在窗口滑动时，左侧元素从队首出队，右侧元素从队尾入队

第一步：构造有序队列

		ArrayList max_nums = new ArrayList();
        
        //设置一个双向队列，队尾用于插入滑动窗口右侧的新元素，队首抛出旧元素
        ArrayDeque window_que = new ArrayDeque();
        for(int i=0; i//第一个窗口的范围为[0,size-1]
            
            
            while(!window_que.isEmpty() && num[window_que.getLast()]
                window_que.pollLast();
            }
            window_que.add(i);//新元素下标从队尾入队
        }
        //获取首个滑动窗口的最大值(位于队首)
        max_nums.add(num[window_que.getFirst()]);

第二步：开始窗口滑动操作，每次滑动后都必须保持队列有序

		//滑动窗口范围为[i-size+1, i]
        for(int i=size; i
            
            
            if(!window_que.isEmpty() && window_que.getFirst()<(i-size+1)){
                window_que.pollFirst();
            }
            
            //新元素从队尾入队前，为了保持递增序同样要让队尾所有小于新元素的元素下标从队尾出队
            while(!window_que.isEmpty() && num[window_que.getLast()]
                window_que.pollLast();
            }
            window_que.add(i);//新元素下标从队尾入队
            
            //获取当前滑动窗口中的最大值，window_que.getFirst()获取有序队列的队首下标
            max_nums.add(num[window_que.getFirst()]);
        }

完整代码

import java.util.*;
public class Solution {
    public ArrayList maxInWindows(int [] num, int size) {
        if(num==null || num.length==0){
            return null;
        }
        
        ArrayList max_nums = new ArrayList();
        
        //设置一个双向队列，队尾用于插入滑动窗口右侧的新元素，队首抛出旧元素
        ArrayDeque window_que = new ArrayDeque();
        for(int i=0; i//第一个窗口的范围为[0,size-1]
            
            
            while(!window_que.isEmpty() && num[window_que.getLast()]
                window_que.pollLast();
            }
            window_que.add(i);//新元素下标从队尾入队
        }
        //获取首个滑动窗口的最大值(位于队首)
        max_nums.add(num[window_que.getFirst()]);
        
        
        //滑动窗口范围为[i-size+1, i]
        for(int i=size; i
            
            
            if(!window_que.isEmpty() && window_que.getFirst()<(i-size+1)){
                window_que.pollFirst();
            }
            
            //新元素从队尾入队前，为了保持递增序同样要让队尾所有小于新元素的元素下标从队尾出队
            while(!window_que.isEmpty() && num[window_que.getLast()]
                window_que.pollLast();
            }
            window_que.add(i);//新元素下标从队尾入队
            
            //获取当前滑动窗口中的最大值，window_que.getFirst()获取有序队列的队首下标
            max_nums.add(num[window_que.getFirst()]);
        }
        
        
        return max_nums;
    }
}

方法二的时间复杂度为O(n)，不排除在某些情况下会下降至O(nm)，但平均效率比起方法一已有显著提升