题目描述
给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{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]}。
解题思路
思路一：极致追求时间效率，O（n） 用3.1中包含Min的栈的思路实现一个包含max的栈，然后用两个这种栈实现一个队列，滑动窗口相当于队列的进队和出队，不断读取max值就可以了，每次读max的时间复杂度为O(1)，总体复杂度为O(n) 思路二：普通解法 用一个双端队列，队列第一个位置保存当前窗口的最大值，当窗口滑动一次 1.判断当前最大值是否过期 2.新增加的值从队尾开始比较，把所有比他小的值丢掉
代码
思路一
import java
.util
.ArrayList
;
import java
.util
.Stack
;
public class GetMaxInWindows {
static class StackWithMax{
Stack
<Integer> stack1
= new Stack();
Stack
<Integer> stack2
= new Stack();
public void push(int ele
){
if (stack1
.size()==0 && stack2
.size()==0){
stack1
.push(ele
);
stack2
.push(ele
);
}else{
stack1
.push(ele
);
if (ele
> stack2
.peek()){
stack2
.push(ele
);
}else{
stack2
.push(stack2
.peek());
}
}
}
public int pop(){
stack2
.pop();
return stack1
.pop();
}
public int getMax(){
return stack2
.peek();
}
public int size(){
return stack1
.size();
}
}
static class QueueWithMax{
private StackWithMax stack1
= new StackWithMax();
private StackWithMax stack2
= new StackWithMax();
public void EnQueue(int ele
){
stack2
.push(ele
);
}
public int DeQueue(){
if (stack1
.size()==0){
while (stack2
.size()>0){
stack1
.push(stack2
.pop());
}
}
return stack1
.pop();
}
public int getMax(){
if (stack1
.size()>0 && stack2
.size()>0)
return Math
.max(stack1
.getMax(), stack2
.getMax());
else if (stack1
.size()>0 && stack2
.size()==0)
return stack1
.getMax();
else if (stack1
.size()==0 && stack2
.size()>0)
return stack2
.getMax();
else
return -1;
}
public int size(){
return stack2
.size() + stack1
.size();
}
}
public static ArrayList
<Integer> maxInWindows(int[] nums
, int size
){
ArrayList
<Integer> res
= new ArrayList<Integer>();
if (nums
== null
|| nums
.length
==0 || size
==0){
return res
;
}
QueueWithMax queue
= new QueueWithMax();
for (int i
=0;i
<nums
.length
;i
++){
if (queue
.size()<size
){
queue
.EnQueue(nums
[i
]);
if (queue
.size()==size
)
res
.add(queue
.getMax());
}else{
queue
.EnQueue(nums
[i
]);
queue
.DeQueue();
res
.add(queue
.getMax());
}
}
return res
;
}
public static void main(String
[] args
) {
int[] data
= new int[]{2,3,4,2,6,2,5,1};
System
.out
.println(maxInWindows(data
, 3));
}
}
思路二
import java
.util
.LinkedList
;
public class Demo07 {
public int[] getMaxOfWindow(int[] arr
, int w
) {
if (arr
== null
|| w
< 1 || arr
.length
< w
) {
return null
;
}
LinkedList
<Integer> qmax
= new LinkedList<>();
int[] res
= new int[arr
.length
- w
+ 1];
int index
= 0;
for (int i
= 0; i
< arr
.length
; i
++) {
while (!qmax
.isEmpty() && arr
[qmax
.peekLast()] <= arr
[i
]) {
qmax
.pollLast();
}
qmax
.addLast(i
);
if (qmax
.peekFirst() == i
- w
) {
qmax
.pollFirst();
}
if (i
>= w
- 1) {
res
[index
++] = arr
[qmax
.peekFirst()];
}
}
return res
;
}
}
