写一个java版本滑动窗口算法
时间: 2023-01-15 13:31:46 浏览: 132
滑动窗口算法
5星 · 资源好评率100%
滑动窗口算法是指,维护一个固定大小的窗口,在数据流上移动这个窗口,并在每次移动后计算窗口中的数据。
下面是一个 Java 版本的滑动窗口算法的实现示例:
```
public int[] slidingWindow(int[] nums, int k) {
if (nums == null || nums.length == 0) return new int[0];
int[] result = new int[nums.length - k + 1];
Deque<Integer> deque = new LinkedList<>();
for (int i = 0; i < nums.length; i++) {
// 维护单调递增队列
while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) deque.pollFirst();
while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) deque.pollLast();
deque.offerLast(i);
if (i >= k - 1) result[i - k + 1] = nums[deque.peekFirst()];
}
return result;
}
```
在这个算法中,使用了双端队列来维护窗口内的数据,保证队列中的数据是单调递增的。每当加入一个新的数据时,都会先将队列中比当前数据小的数据弹出,然后再将当前数据加入队列。在每次移动窗口时,也会将队列中已经不在窗口内的数据弹出。
这个算法的时间复杂度为 O(n),可以在数据量比较大的情况下较快地处理数据。
阅读全文