文档章节

滑动窗口的最大值

初雪之音
 初雪之音
发布于 2017/05/15 19:58
字数 420
阅读 21
收藏 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}的滑动窗口有以下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]}。

思路一

import java.util.*;

class ListNode {
	int val;
	ListNode next;

	ListNode(int x) {
		val = x;
	}
}

class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;

	TreeNode(int x) {
		val = x;
	}
}

public class Solution {
	class StackWithMax {
		Stack<Integer> m_data = new Stack<>();
		Stack<Integer> m_max = new Stack<>();

		public void push(int e) {
			m_data.push(e);
			if (m_max.isEmpty() || m_max.peek() < e) {
				m_max.push(e);
			} else {
				m_max.push(m_max.peek());
			}
		}

		public int peek() {
			int result = 0;

			if (!m_data.isEmpty()) {
				result = m_data.peek();
			}

			return result;
		}

		public void pop() {
			if (!m_data.isEmpty()) {
				m_data.pop();
				m_max.pop();
			}
		}

		public int max() {
			int result = 0;
			if (!m_max.isEmpty()) {
				result = m_max.peek();
			}
			return result;
		}

		public boolean isEmpty() {
			return m_data.isEmpty();
		}
	}

	class QueueWithMax {
		StackWithMax input = new StackWithMax();
		StackWithMax output = new StackWithMax();

		public void push(int e) {
			input.push(e);
		}

		public int peek() {
			int result = 0;
			if (output.isEmpty()) {
				while (!input.isEmpty()) {
					output.push(input.peek());
					input.pop();
				}
			}
			if (!output.isEmpty()) {
				result = output.peek();
			}
			return result;
		}

		public void pop() {
			if (output.isEmpty()) {
				peek();
			}
			output.pop();
		}

		public int max() {
			return Math.max(input.max(), output.max());
		}

		public boolean isEmpty() {
			return input.isEmpty() && output.isEmpty();
		}
	}

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

		if (num != null && num.length >= size && size!=0) {
			QueueWithMax queue = new QueueWithMax();
			for (int i = 0; i < num.length; i++) {
				queue.push(num[i]);
				if (i >= size) {
					queue.pop();
					list.add(queue.max());
				} else if(i == size-1){
					list.add(queue.max());
				}
			}
		}

		return list;
	}

	public static void main(String[] args) {
		Solution sou = new Solution();
		int[] num = { 2, 3, 4, 2, 6, 2, 5, 1 };
		for (int n : sou.maxInWindows(num, 0)) {
			System.out.print(n + " ");
		}
	}
}

思路二

import java.util.*;

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

		if (num != null && num.length >= size && size > 0) {
			Deque<Integer> dq = new LinkedList<>();
			for (int i = 0; i < size; i++) {
				while (!dq.isEmpty() && num[dq.getLast()] < num[i]) {
					dq.removeLast();
				}
				dq.addLast(i);
			}
			list.add(num[dq.getFirst()]);
			for (int i = size; i < num.length; i++) {
				while (!dq.isEmpty() && num[dq.getLast()] < num[i]) {
					dq.removeLast();
				}
				dq.addLast(i);
				if (dq.getFirst() < i - size + 1) {
					dq.removeFirst();
				}
				list.add(num[dq.getFirst()]);
			}
		}

		return list;
	}
}

 

© 著作权归作者所有

共有 人打赏支持
初雪之音
粉丝 44
博文 265
码字总数 148651
作品 0
广州
程序员
[剑指offer] 滑动窗口的最大值

本文首发于我的个人博客:[尾尾部落](https://weiweiblog.cn/maxinwindows/) 题目描述 给定一个数组和滑动窗口的大小,找出所有滑动窗口里数值的最大值。例如,如果输入数组{2,3,4,2,6,2,5,...

繁著
07/25
0
0
Nginx 高并发TCP请求Linux系统参数配置

需要修改/etc/sysctl.conf来更改内核参数 #原有字段 net.ipv4.tcp_syncookies = 1 新增字段 fs.file-max = 999999 net.ipv4.tcptwreuse = 1 net.ipv4.tcpkeepalivetime = 600 net.ipv4.tcpf......

满小茂
2015/12/28
742
0
吴恩达 DeepLearning.ai 课程提炼笔记(4-3)卷积神经网络 --- 目标检测

以下为在Coursera上吴恩达老师的 deeplearning.ai 课程项目中,第四部分《卷积神经网络》第三周课程“目标检测”关键点的笔记。本次笔记几乎涵盖了所有视频课程的内容。在阅读以下笔记的同时...

大树先生
2017/11/22
0
0
nginx-网络优化

我们通常会根据业务特点来进行调整,当Nginx作为静态Web内容服务器、反向代理服务器或是提供图片缩略图功能(实时压缩图片)的服务器时,其内核参数的调整都是不同的。这里只针对最通用的、使...

妙曼
2017/07/25
0
0
nginx优化篇之Linux 内核参数的优化 (2)

原博客地址(欢迎访问):http://www.loveyqq.tk/blog/2014/05/27/nginxyou-hua-pian-zhi-linux-nei-he-can-shu-de-you-hua/ 由于默认的Linux内核参数考虑的是最通用的场景,这明显不符合用于支...

NILYANG
2015/04/16
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Confluence 6 识别慢性能的宏

Page Profiling 给你了有关页面在载入的时候操作缓慢的邪教,你可以将下面的内容添加到调试(debug)级别: Version 3.1 及其后续版本 设置包名字为 com.atlassian.renderer.v2.components.M...

honeymose
11分钟前
0
0
day93-20180920-英语流利阅读-待学习

时尚之觞:外表光鲜靓丽,其实穷得要命 Lala 2018-09-20 1.今日导读 讲到时尚界,我们脑海里浮现的可能都是模特和设计师光鲜靓丽、从容潇洒的模样。可是,最近在法国出版的一本书却颠覆了我们...

飞鱼说编程
26分钟前
0
0
maven的pom.xml用解决版本问题

maven管理库依赖,有个好处就是连同库的依赖的全部jar文件一起下载,免去手工添加的麻烦,但同时也带来了同一个jar会被下载了不同版本的问题,好在pom的配置里面允许用<exclusion>来排除一些...

JAVA码猿
50分钟前
1
0
20180920 rzsz传输文件、用户和用户组相关配置文件与管理

利用rz、sz实现Linux与Windows互传文件 [root@centos01 ~]# yum install -y lrzsz # 安装工具sz test.txt # 弹出对话框,传递到选择的路径下rz # 回车后,会从对话框中选择对应的文件传递...

野雪球
今天
2
0
OSChina 周四乱弹 —— 毒蛇当辣条

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @ 达尔文:分享花澤香菜/前野智昭/小野大輔/井上喜久子的单曲《ミッション! 健?康?第?イチ》 《ミッション! 健?康?第?イチ》- 花澤香菜/前野智...

小小编辑
今天
42
11

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部