import java.util.*;
public class Test01 {
public static void main(String[] args) {
int[] num = new int[]{2,3,4,2,6,2,5,1};
int size = 3;
List<Integer> list = maxInWindows(num,size);
System.out.println(list);
}
public static ArrayList<Integer> maxInWindows(int [] num, int size) {
ArrayList<Integer> res = new ArrayList<>();
if (size < 1 || size > num.length){
return res;
}
Deque<Integer> deque = new LinkedList<>();
for (int i = 0; i < num.length; i++) {
// i 其实就是窗口的右边界
//队列添加元素，添加之前先将队列中小于自己的元素剔除
//保证队列的左节点总是窗口中的最大值，保证队列是从左到右是单调递减的
while (!deque.isEmpty() && num[deque.getLast()] < num[i]){
deque.pollLast();
}
//注意添加的是元素下标
deque.addLast(i);
//队列中只能存窗口里的元素，当窗口划走后，需要将元素剔除
while (!deque.isEmpty() && deque.getFirst() <= i - size){
deque.pollFirst();
}
//将窗口中的最大值保存，i为窗口的右边界
if (i >= size - 1){
res.add(num[deque.getFirst()]);
}
}
return res;
}
}滑动窗口
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- Flink的窗口机制是其底层核心之一，也是高效流处理的关键。Flink窗口分配的基类是WindowAssigner...
- 算法 单调队列 题目描述 给出一个数组，有固定大小窗口在数组上从左到右滑动，现要求求出每个窗口中最大值与最小值。 ...
- 基本认识 滑动窗口算法的本质是双指针法中的左右指针法,滑动窗口算法是双指针法中的左右指针法更为形象的一种表达方式。...
