滑动窗口的最大值
给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{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]}。
思路
思路
遍历数组，将数存放在双向队列中，并用L,R来标记窗口的左边界和右边界。队列中保存的并不是真的数，而是该数值对应的数组下标位置，并且数组中的数要从大到小排序。如果当前遍历的数比队尾的值大，则需要弹出队尾值，直到队列重新满足从大到小的要求。刚开始遍历时，L和R都为0，有一个形成窗口的过程，此过程没有最大值，L不动，R向右移。当窗口大小形成时，L和R一起向右移，每次移动时，判断队首的值的数组下标是否在[L,R]中，如果不在则需要弹出队首的值，当前窗口的最大值即为队首的数。
示例
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释过程中队列中都是具体的值，方便理解，具体见代码。
初始状态：L=R=0,队列:{}
i=0,nums[0]=1。队列为空,直接加入。队列：{1}
i=1,nums[1]=3。队尾值为1，3>1，弹出队尾值，加入3。队列：{3}
i=2,nums[2]=-1。队尾值为3，-1<3，直接加入。队列：{3,-1}。此时窗口已经形成，L=0,R=2，result=[3]
i=3,nums[3]=-3。队尾值为-1，-3<-1，直接加入。队列：{3,-1,-3}。队首3对应的下标为1，L=1,R=3，有效。result=[3,3]
i=4,nums[4]=5。队尾值为-3，5>-3，依次弹出后加入。队列：{5}。此时L=2,R=4，有效。result=[3,3,5]
i=5,nums[5]=3。队尾值为5，3<5，直接加入。队列：{5,3}。此时L=3,R=5，有效。result=[3,3,5,5]
i=6,nums[6]=6。队尾值为3，6>3，依次弹出后加入。队列：{6}。此时L=4,R=6，有效。result=[3,3,5,5,6]
i=7,nums[7]=7。队尾值为6，7>6，弹出队尾值后加入。队列：{7}。此时L=5,R=7，有效。result=[3,3,5,5,6,7]
通过示例发现R=i，L=k-R。由于队列中的值是从大到小排序的，所以每次窗口变动时，只需要判断队首的值是否还在窗口中就行了。
解释一下为什么队列中要存放数组下标的值而不是直接存储数值，因为要判断队首的值是否在窗口范围内，由数组下标取值很方便，而由值取数组下标不是很方便。
public class Test6 {
public static void main(String[] args) {
int[] nums = {1,3,-1,-3,5,3,6,7};
System.out.println(Arrays.toString(maxSlidingWindow(nums,3)));
}
public static int[] maxSlidingWindow(int[] nums, int k) {
if(nums.length == 0 || k == 0) {
return new int[0];
}
Deque<Integer> deque = new LinkedList<>();
int[] res = new int[nums.length - k + 1];
for(int i = 0; i < k; i++) {
// 未形成窗口
while(!deque.isEmpty() && deque.peekLast() < nums[i]) {
deque.removeLast();
}
deque.addLast(nums[i]);
}
res[0] = deque.peekFirst();
for(int i = k; i < nums.length; i++) {
// 形成窗口后
if(deque.peekFirst() == nums[i - k]){
deque.removeFirst();
}
while(!deque.isEmpty() && deque.peekLast() < nums[i]){
deque.removeLast();
}
deque.addLast(nums[i]);
res[i - k + 1] = deque.peekFirst();
}
return res;
}
}
方法1 双栈
实际上一个滑动窗口可以看成是一个队列。当窗口滑动时，处于窗口的第一个数字被删除，同时在窗口的末尾添加一个新的数字。这符合队列的先进先出特性。如果能从队列中找出它的最大数，这个问题也就解决了。
在面试题21中。我们实现了一个可以用O(1)时间得到最小值的栈。同样，也可以用O(1)时间得到栈的最大值。同时在面试题7中，我们讨论了如何用两个栈实现一个队列。综合这两个问题的解决方法，我们发现如果把队列用两个栈实现，由于可以用O(1)时间得到栈中的最大值，那么也就可以用O(1)时间得到队列的最大值，因此总的时间复杂度也就降到了O(n)。
方法1 两端开口的队列
接着以输入数字{2,3,4,2,6,2,5,1}为例一步分析。
数组的第一个数字是2，把它存入队列中。第二个数字是3.由于它比前一个数字2大，因此2不可能成为滑动窗口中的最大值。2先从队列里删除，再把3存入到队列中。此时队列中只有一个数字3.针对第三个数字4的步骤类似，最终在队列中只剩下一个数字4.此时滑动窗口中已经有3个数字，而它的最大值4位于队列的头部。
接下来处理第四个数字2。2比队列中的数字4小。当4滑出窗口之后2还是有可能成为滑动窗口的最大值，因此把2存入队列的尾部。现在队列中有两个数字4和2，其中最大值4仍然位于队列的头部。
下一个数字是6.由于它比队列中已有的数字4和2都大，因此这时4和2已经不可能成为滑动窗口中的最大值。先把4和2从队列中删除，再把数字6存入队列。这个时候最大值6仍然位于队列的头部。
第六个数字是2.由于它比队列中已有的数字6小，所以2也存入队列的尾部。此时队列中有两个数字，其中最大值6位于队列的头部。
接下来的数字是5.在队列中已有的两个数字6和2里，2小于5，因此2不可能是一个滑动窗口的最大值，可以把它从队列的尾部删除。删除数字2之后，再把数字5存入队列。此时队列里剩下两个数字6和5，其中位于队列头部的是最大值6.
数组最后一个数字是1，把1存入队列的尾部。注意到位于队列头部的数字6是数组的第5个数字，此时的滑动窗口已经不包括这个数字了，因此应该把数字6从队列删除。那么怎么知道滑动窗口是否包括一个数字？应该在队列里存入数字在数组里的下标，而不是数值。当一个数字的下标与当前处理的数字的下标之差大于或者等于滑动窗口的大小时，这个数字已经从滑动窗口中滑出，可以从队列中删除了。
队列：
队列（简称作队，Queue）也是一种特殊的线性表，队列的数据元素以及数据元素间的逻辑关系和线性表完全相同，其差别是线性表允许在任意位置插入和删除，而队列只允许在其一端进行插入操作在其另一端进行删除操作。
队列中允许进行插入操作的一端称为队尾，允许进行删除操作的一端称为队头。队列的插入操作通常称作入队列，队列的删除操作通常称作出队列。
下图是一个依次向队列中插入数据元素a0,a1,...,an-1后的示意图：
/**************************************************************
* Copyright (c) 2016,
* All rights reserved.
* 版 本 号：v1.0
* 题目描述：给定一个数组和滑动窗口的大小，请找出所有滑动窗口里的最大值。如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，
* 那么一共存在6个滑动窗口，他们的最大值分别为{4.4,6,6,6,5}。
* 输入描述：请输入一个数组：以空格隔开
* 2 3 4 2 6 2 5 1
* 请输入滑动窗口的大小：
* 3
* 程序输出： 滑动窗口的最大值为：
* [4, 4, 6, 6, 6, 5]
* 问题分析： 队列：队列中允许进行插入操作的一端称为队尾，允许进行删除操作的一端称为队头。队列的插入操作通常称作入队列，队列的删除操作通常称作出队列。
* 算法描述：见程序
* 完成日期：2016-10-18
***************************************************************/
package org.marsguo.offerproject65;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Scanner;
class SolutionMethod1{
public ArrayList<Integer> maxInWindows(int[] num,int size){
ArrayList<Integer> ret = new ArrayList<>();
if(num == null){
return ret;
}
if(num.length < size || size < 1){
return ret;
}
LinkedList<Integer> indexDeque = new LinkedList<>(); //用于保存滑动窗口中的数字
/*
滑动窗口内部，用于判断窗口中的最大值
*/
for(int i = 0; i < size - 1; i++){
while(!indexDeque.isEmpty()&& num[i] > num[indexDeque.getLast()]){ //getLast为插入端
indexDeque.removeLast(); //将前面比K小的直接移除队列，因为不可能成为滑动窗口的最大值
}
indexDeque.addLast(i); //将数字存入滑动窗口中
}
/*
滑动整个窗口
*/
for(int i = size - 1; i < num.length; i++){
while(!indexDeque.isEmpty() && num[i] > num[indexDeque.getLast()]){ //getLast为插入端，队尾
indexDeque.removeLast(); //将前面比K小的直接移除队列，因为不可能成为滑动窗口的最大值
}
indexDeque.addLast(i);
//System.out.println("indexDeque = " + indexDeque.getFirst() + ",i = " + i); //getFirst为允许删除端，队头
if(i - indexDeque.getFirst() + 1 > size){
indexDeque.removeFirst();
}
ret.add(num[indexDeque.getFirst()]); //每次添加的是num[indexDeque.getFirst()],而不是indexDeque.getFirst().
}
return ret;
}
}
public class MaxInWindows {
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
System.out.println("请输入一个数组：以空格隔开");
String str = scanner.nextLine();
System.out.println("请输入滑动窗口的大小：");
int k = scanner.nextInt();
String[] tmp = str.split(" ");
int[] arrays = new int[tmp.length];
for(int i = 0; i < tmp.length;i++){
arrays[i] = Integer.parseInt(tmp[i]);
}
scanner.close();
SolutionMethod1 solution1 = new SolutionMethod1();
System.out.println("滑动窗口的最大值为：");
System.out.println(solution1.maxInWindows(arrays, k));
}
}思路2
* 1、双端队列保存滑动窗口的最大值(保存在头部)，次大值数据
* 2、窗口滑动，从右侧遍历，比当前值小的移出队列，队首元素过期 移出队列，
* 当前元素的索引加入队列
package com.codinginterviews.array;
import java.util.ArrayDeque;
import java.util.ArrayList;
/**
* 题目：
* 滑动窗口的最大值 -- newcoder 剑指Offer 64
*
* 题目描述：
*
给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。
例如，如果输入数组{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 MaxInWindows {
/**
* 思路：
* 1、遍历数组，每次取滑动窗口的所有值，遍历窗口中的元素，取出最大值
*/
public ArrayList<Integer> maxInWindows(int [] num, int size) {
ArrayList<Integer> res = new ArrayList<>();
if (num == null || size <= 0 || num.length < size) {
return res;
}
// 暴力破解法
int len = num.length;
int maxIdx = len - size;
for (int i=0; i<= maxIdx; i++) {
// 获取当前序列的最大值
int curMax = num[i];
for (int j=i+1; j<i+size; j++) {
curMax = curMax > num[j] ? curMax : num[j];
}
// 最大值加入res
res.add(curMax);
}
return res;
}
/**
* 思路：
* 1、双端队列保存滑动窗口的最大值(保存在头部)，次大值数据
* 2、窗口滑动，从右侧遍历，比当前值小的移出队列，队首元素过期 移出队列，
* 当前元素的索引加入队列
*/
public ArrayList<Integer> maxInWindowsII(int [] num, int size) {
ArrayList<Integer> res = new ArrayList<>();
if (num == null || size <= 0 || num.length < size) {
return res;
}
// 使用双端队列 缓存滑动窗口，最大值保存在头部
ArrayDeque<Integer> queue = new ArrayDeque<>();
int len = num.length;
for (int i=0; i<len; i++){
// 从后面依次弹出队列中比当前num值小的元素，同时也能保证队列首元素为当前窗口最大值下标
while(!queue.isEmpty() && num[queue.peekLast()]<=num[i]) {
queue.pollLast();
}
// 当队首元素坐标对应的num不在窗口中，需要弹出
if(!queue.isEmpty() && i-queue.peekFirst()+1>size) {
queue.pollFirst();
}
// 把每次滑动的num下标加入队列
queue.offerLast(i);
// 当滑动窗口首地址i大于等于size时才开始写入窗口最大值
if(i+1 >= size) {
res.add(num[queue.peekFirst()]);
}
}
return res;
}
public static void main(String[] args) {
int[] num = {2,3,4,2,6,2,5,1};
int size = 3;
System.out.println(new MaxInWindows().maxInWindows(num, size));
System.out.println(new MaxInWindows().maxInWindowsII(num, size));
}
}
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> maxInWindows(int [] num, int size)
{
ArrayList<Integer> returnlist = new ArrayList<>();
if(num == null || size==0){
return returnlist;
}
int numlength = num.length;
for(int i =0;i< numlength-size+1;i++){
int maxNub =0;
for(int j=i;j< size+i;j++){
if(num[j] >maxNub){
maxNub = num[j];
}
}
returnlist.add(maxNub);
}
return returnlist;
}
}
京公网安备 11010502036488号