首页 > 数据结构 > 线性结构 > 数组滑动窗口中的最大值[单调队列]
2014
07-11

数组滑动窗口中的最大值[单调队列]

给定大小为N的数组。数组被分为大小为k的子数组,找到每个子数组的最大值。子数组即为滑动窗口。

如果数组为1 2 3 4 5 6,k=2.

子数组为1 2; 2 3; 3 4; 4 5; 5 6

例如:

Input :
arr[] = {1, 2, 3, 1, 4, 5, 2, 3, 6}
k = 3
Output :
3 3 4 5 5 5 6

Input :
arr[] = {8, 5, 10, 7, 9, 4, 15, 12, 90, 13}
k = 4
Output :
10 10 10 15 15 90 90

方法1  直接计算

使用一个两层循环,即可遍历所有的子数组,并找出其中的最大值。

#include<stdio.h>

void printKMax(int arr[], int n, int k)
{
    int j, max;

    for (int i = 0; i <= n-k; i++)
    {
        max = arr[i];

        for (j = 1; j < k; j++)
        {
            if (arr[i+j] > max)
               max = arr[i+j];
        }
        printf("%d ", max);
    }
}

int main()
{
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int n = sizeof(arr)/sizeof(arr[0]);
    int k = 3;
    printKMax(arr, n, k);
    return 0;
}

时间复杂度为 O(nk).

方法2 使用平衡二叉树

1) 取出数组中的前K个元素,构建一个平衡二叉树,可以用红黑树或AVL树。

2) 循环 i=0 到 n-k

a) 从二叉树中取出最大的元素,并打印

b) 在二叉树中搜索 arr[i]并删除

c) 将 arr[i+k]插入二叉树

第一步的操作复杂度为O(kLogk),由于循环体每次操作都是lgk,因此总的复杂度为 O(nLogk),总的复杂度为 O(kLogk + (n-k+1)*Logk) ,也就是O(nLogk).

方法3 使用双端队列

创建一个双端队列deque,deque只存储当前的窗口中有用的元素,有用也就是会对未来的选择有影响的元素。插入时保证下面两个性质:

1) 首先,我们保证每次都是队尾插入元素,也就是队首的元素的肯定是距离当前元素最远的。因此每次滑动窗口,只判断队首元素是否超出窗口范围,超出的话则删除。

2) 然后保证deque中的元素是升序的,队尾是最小的元素。由于是从队尾插入,只需要把队尾的元素和当前元素比较即可,不符合条件,则删除队尾元素。

为了判断元素是否超出窗口范围,我们需要存储元素下标。

这种队列,又叫做单调队列,练手题目:POJ 2823

下面是java代码的实现:

import java.util.Deque;
import java.util.LinkedList;

public class MaximumSubArrK {

	static void printKMax(int arr[],int k){
		Deque<Integer> deque = new LinkedList<Integer>();
		for(int i=0; i < arr.length; i++){
			while(!deque.isEmpty() && (i-deque.peekFirst()>=k) )
				deque.pollFirst();
			while(!deque.isEmpty() && arr[deque.peekLast()] <= arr[i] )
				deque.pollLast();
			deque.addLast(i);
			if(i >= k-1)
				System.out.print(arr[ deque.peekFirst() ] + ",");
		}
		System.out.println();
	}

	public static void main(String[] args) {
		int arr[] =  {8, 5, 10, 7, 9, 4, 15, 12, 90, 13};
		printKMax(arr ,4);

	}
}

输出:

10,10,10,15,15,90,90,

时间复杂度为 O(n)。 因为每个元素都最多会被入队列和出队列一次,总的操作次数不会超过2n。


  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  2. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。