文档章节

滑动窗口的最大值

初雪之音
 初雪之音
发布于 2017/05/15 19:58
字数 420
阅读 21
收藏 0
点赞 0
评论 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;
	}
}

 

© 著作权归作者所有

共有 人打赏支持
初雪之音
粉丝 42
博文 265
码字总数 148651
作品 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
9-滑动条(滚动条)创建与实现;createTrackbar()函数

在前几节的讲解中,我们若想换个演示结果,就需要每次在程序里修改参数值,然后再次运行此程序,用起来很麻烦,若是可以在窗口中实时调整参数值,从而显示结果岂不是很方便。 OpenCV里提供了...

weixin_40807247
04/17
0
0
Coursera吴恩达《卷积神经网络》课程笔记(3)-- 目标检测

我的CSDN博客地址:红色石头的专栏 我的知乎主页:红色石头 我的知乎专栏:红色石头的机器学习之路 欢迎大家关注我!共同学习,共同进步! 《Convolutional Neural Networks》是Andrw Ng深度...

红色石头
01/12
0
0
nginx服务器Linux内核参数优化

由于默认的Linux内核参数考虑的是最通用的场景,这明显不符合用于支持高并发访问的Web服务器的定义,所以需要修改Linux内核参数,使得Nginx可以拥有更高的性能。 在优化内核时,可以做的事件...

Foundation
2015/12/21
62
0
目标检测 - -DeepLearning.ai 学习笔记(4-3)

课程笔记地址:https://mp.csdn.net/postlist 课程代码地址:https://github.com/duboya/DeepLearning.ai-pragramming-code/tree/master 欢迎大家fork及star!(-^O^-) 卷积神经网络 — 目标检......

dby_freedom
04/09
0
0
Sliding Window Maximum

from https://leetcode.com/problems/sliding-window-maximum/ Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very r......

BlueWoods
2015/07/18
0
0
cv::createTrackbar cv::threshold

#include <iostream> include <glog/logging.h> include <opencv2/highgui/highgui.hpp> include <opencv2/imgproc/imgproc.hpp> include <stdlib.h> using namespace std; cv::Mat image, g......

元禛慎独
2016/10/20
20
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

实现异步有哪些方法

有哪些方法可以实现异步呢? 方式一:java 线程池 示例: @Test public final void test_ThreadPool() throws InterruptedException { ScheduledThreadPoolExecutor scheduledThre......

黄威
今天
0
0
linux服务器修改mtu值优化cpu

一、jumbo frames 相关 1、什么是jumbo frames Jumbo frames 是指比标准Ethernet Frames长的frame,即比1518/1522 bit大的frames,Jumbo frame的大小是每个设备厂商规定的,不属于IEEE标准;...

六库科技
今天
0
0
牛客网刷题

1. 二维数组中的查找(难度:易) 题目描述 在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入...

大不了敲一辈子代码
今天
0
0
linux系统的任务计划、服务管理

linux任务计划cron 在linux下,有时候要在我们不在的时候执行一项命令,或启动一个脚本,可以使用任务计划cron功能。 任务计划要用crontab命令完成 选项: -u 指定某个用户,不加-u表示当前用...

黄昏残影
昨天
0
0
设计模式:单例模式

单例模式的定义是确保某个类在任何情况下都只有一个实例,并且需要提供一个全局的访问点供调用者访问该实例的一种模式。 实现以上模式基于以下必须遵守的两点: 1.构造方法私有化 2.提供一个...

人觉非常君
昨天
0
0
《Linux Perf Master》Edition 0.4 发布

在线阅读:https://riboseyim.gitbook.io/perf 在线阅读:https://www.gitbook.com/book/riboseyim/linux-perf-master/details 百度网盘【pdf、mobi、ePub】:https://pan.baidu.com/s/1C20T......

RiboseYim
昨天
1
0
conda 换源

https://mirrors.tuna.tsinghua.edu.cn/help/anaconda/ conda config --add channels https://mirrors.tuna.tsinghua.edu.cn/anaconda/pkgs/free/conda config --add channels https://mir......

阿豪boy
昨天
1
0
Confluence 6 安装补丁类文件

Atlassian 支持或者 Atlassian 缺陷修复小组可能针对有一些关键问题会提供补丁来解决这些问题,但是这些问题还没有放到下一个更新版本中。这些问题将会使用 Class 类文件同时在官方 Jira bug...

honeymose
昨天
0
0
非常实用的IDEA插件之总结

1、Alibaba Java Coding Guidelines 经过247天的持续研发,阿里巴巴于10月14日在杭州云栖大会上,正式发布众所期待的《阿里巴巴Java开发规约》扫描插件!该插件由阿里巴巴P3C项目组研发。P3C...

Gibbons
昨天
1
0
Tomcat介绍,安装jdk,安装tomcat,配置Tomcat监听80端口

Tomcat介绍 Tomcat是Apache软件基金会(Apache Software Foundation)的Jakarta项目中的一个核心项目,由Apache、Sun和其他一些公司及个人共同开发而成。 java程序写的网站用tomcat+jdk来运行...

TaoXu
昨天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部