当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

单调队列-用一个长度为k的窗在整数数列上移动,求窗里面所包含的数的最大值

发表于: 2012-11-11   作者:bylijinnan   来源:转载   浏览:
摘要: import java.util.LinkedList; /* 单调队列 滑动窗口 单调队列是这样的一个队列:队列里面的元素是有序的,是递增或者递减 题目:给定一个长度为N的整数数列a(i),i=0,1,...,N-1和窗长度k. 要求:f(i) = max{a(i-k+1),a(i-k+2),..., a(i)},i = 0,1,...,N-1 问题的另一种描述就
import java.util.LinkedList;

/*

单调队列 滑动窗口
单调队列是这样的一个队列:队列里面的元素是有序的,是递增或者递减

题目:给定一个长度为N的整数数列a(i),i=0,1,...,N-1和窗长度k.

要求:f(i) = max{a(i-k+1),a(i-k+2),..., a(i)},i = 0,1,...,N-1

问题的另一种描述就是用一个长度为k的窗在整数数列上移动,求窗里面所包含的数的最大值

详情见 
@陈利人 http://weibo.com/lirenchen
http://weibo.com/1915548291/z3T4HbRRr 
该条微博下有人回复说:
@我是RickyYang:维护一个有k个元素大顶堆,如果每次移出堆的是堆顶,那么将新数替换堆顶,并对堆做调整,
如果移出不是堆顶,则只需将新数和堆顶比较,大的留在堆顶,小的替换移出的数,无需调整堆。最坏的话时间复杂度nlogk,最好n-k+logk (11月6日 08:22)

这应该也是可行的。我的刚开始想到的也是用最大堆。不过稍嫌麻烦的是:“如果移出不是堆顶,则只需将新数和堆顶比较,大的留在堆顶,小的替换移出的数”
这样的话,要记录窗口移动后被移出窗口的那个数,同时“替换移出的数”,要在最大堆执行搜索

单调队列的参考思路:
http://xuyemin520.is-programmer.com/posts/25964

1.首先看插入元素:为了保证队列的递减性,我们在插入元素v的时候,要将队尾的元素和v比较,
如果队尾的元素不大于v,则删除队尾的元素,然后继续将新的队尾的元素与v比较,直到队尾的元素大于v,这个时候我们才将v插入到队尾

2.队尾的删除刚刚已经说了,那么队首的元素什么时候删除呢?
由于我们只需要保存i的前k-1个元素中的最大值,所以当队首的元素的索引或下标小于 i-k+1的时候,
就说明队首的元素对于求f(i)已经没有意义了,因为它已经不在窗里面了。所以当index[队首元素]<i-k+1时,将队首 元素删除

在下面的代码里面,实现队列时,我直接用了LinkedList,因为手工用数组维护一个单调队列要考虑挺多的。现在把重点放在算法的思路上^_^

*/
public class SlidingWindow {

	public static void main(String[] args) {
		/*
		int[] array = { 8, 7, 12, 5, 16, 9, 17, 2, 4, 6 };
		int k = 3;
		 */
		
		int[] array = { 3, 4, 5, 7, 3, 5, 2, 9 };
		int k = 3;
		
		int[] max = maxInWindow(array, k);
		for (int i : max) {
			System.out.println(i);
		}
	}

	public static int[] maxInWindow(int[] array, int k) {
		if (k <= 0 || array == null || array.length == 0) {
			System.out.println("invalid input");
			return new int[0];
		}
		int len = array.length;
		int[] max = new int[len];
		if (k == 1) {
			System.arraycopy(array, 0, max, 0, len);	//复制一份,不影响原数组
		} else {
			LinkedList<Item> queue = new LinkedList<Item>();
			for (int i = 0; i < len; i++) {
				Item curItem = new Item(array[i], i);
				if (queue.isEmpty()) {
					queue.addLast(curItem);
				} else {
					Item head = queue.getFirst();
					int headIndex = head.getIndex();
					
					//如果队首元素已不在窗口内,则删除
					if (headIndex < (i - k + 1)) {	
						queue.removeFirst();
					}
					
					//插入元素
					while (!queue.isEmpty()) {
						Item tail = queue.getLast();
						int tailValue = tail.getValue();
						if (tailValue < array[i]) {
							queue.removeLast();
							if (queue.isEmpty()) {
								queue.addLast(curItem);
								break;
							}
						} else if (tailValue > array[i]) {
							queue.addLast(curItem);
						} else {
							break;
						}
					}
				}
				
				//每次操作后,队首元素为当前窗口的最大值
				if (!queue.isEmpty()) {
					max[i] = queue.getFirst().getValue();
				}
			}
		}
		return max;
	}

}

class Item {
	
	//数组元素值
	private int value;
	
	//数组元素对应的下标
	private int index;

	public Item(int value, int index) {
		this.value = value;
		this.index = index;
	}

	public int getValue() {
		return value;
	}

	public int getIndex() {
		return index;
	}

}

单调队列-用一个长度为k的窗在整数数列上移动,求窗里面所包含的数的最大值

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
一个整数数组,长度为n,将其分为m 份,使各份的和相等,求m 的最大值 比如{3,2,4,3,6} 可以分
/* * Copyright (c) 2012, 烟台大学计算机学院 * All rights reserved. * 作 者: 王俊 * 完成日期
/* * Copyright (c) 2012, 烟台大学计算机学院 * All rights reserved. * 作 者: 杨绍宁 * 完成日
/* (程序头部注释开始) * 程序的版权和版本声明部分 * Copyright (c) 2011, 烟台大学计算机学院学生
【解法一】 我们先假设元素的数量不大,例如在几千个左右,在这种情况下,那我们就排序一下吧。在这
开发工具:VC6 开发语言:C++ 第一步:新建对话框应用程序 布局界面效果 第二步:添加控件相关变量
上机内容:C++程序的编写和运行 上机目的:掌握简单C++程序的编辑、编译、连接和运行的一般过程 我
#include<iostream> using namespace std; int main() { int a,b,c,d,t; cout<<"请输入
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespa
今天为大家介绍一款简单的弹出窗。大家在浏览网页的时候就会遇到某些提示信息或者是警告信息,这些
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号