滑动窗口的最大值
滑动窗口的最大值
初雪之音 发表于9个月前
滑动窗口的最大值
  • 发表于 9个月前
  • 阅读 14
  • 收藏 0
  • 点赞 0
  • 评论 0

新睿云服务器60天免费使用,快来体验!>>>   

题目描述

给定一个数组和滑动窗口的大小,找出所有滑动窗口里数值的最大值。例如,如果输入数组{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;
	}
}

 

  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 39
博文 235
码字总数 135019
×
初雪之音
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: