下面列出了java.util.ArrayDeque#peekFirst ( ) 实例代码,或者点击链接到github查看源代码,也可以在右侧发表评论。
/**
* 滑动窗口应当是队列,但为了得到滑动窗口的最大值,队列序可以从两端删除元素,因此使用双端队列。 对新来的元素k,将其与双端队列中的元素相比较
* 1)前面比k小的,直接移出队列(因为不再可能成为后面滑动窗口的最大值了!), 2)前面比k大的X,比较两者下标,判断X是否已不在窗口之内,不在了,直接移出队列
* 队列的第一个元素是滑动窗口中的最大值
*/
public ArrayList<Integer> maxInWindows(int[] num, int size) {
ArrayList<Integer> list = new ArrayList<>();
if (size == 0) return list;
int start = 0;
// 用来保存可能是滑动窗口最大值的数字的下标
ArrayDeque<Integer> index = new ArrayDeque<>();
for (int i = 0; i < num.length; i++) {
start = i - size + 1;
if (index.isEmpty()) index.add(i);
// 如果队列的头部元素已经从滑动窗口里滑出,滑出的数字需要从队列的头部删除
else if (start > index.peekFirst()) index.pollFirst();
// 数组:{2,3,4,2,6,2,5,1}
// 如果已有数字小于待存入的数据, 这些数字已经不可能是滑动窗口的最大值
// 因此它们将会依次地从队尾删除
while ((!index.isEmpty()) && num[index.peekLast()] <= num[i]) index.pollLast();
index.add(i);
if (start >= 0) list.add(num[index.peekFirst()]);
}
return list;
}
public static void findMaximumSlidingWindow(int[] arr,
int windowSize) {
if (arr.length < windowSize) return;
ArrayDeque<Integer> list = new ArrayDeque();
for (int i = 0; i < windowSize; i++) {
while (!list.isEmpty() && arr[i] >= arr[list.peekLast()]) {
list.removeLast();
}
list.addLast(i);
}
System.out.print(arr[list.peekFirst()] + " ");
for (int i = windowSize; i < arr.length; i++) {
while (!list.isEmpty() && arr[i] >= arr[list.peekLast()]) {
list.removeLast();
}
if (!list.isEmpty() && list.peekFirst() <= i - windowSize) {
list.removeFirst();
}
list.addLast(i);
System.out.print(arr[list.peekFirst()] + " ");
}
}
/**
* Finds the maximum element in each and every sub-array
* in {@param a} of size {@param k}.
* <p>
* Time complexity: O(n)
* Auxiliary Space: O(k)
*
* @param a
* @param k
* @return
*/
public static int[] maxInAllSubArraysOfSizeK(int[] a, int k) {
int i, j = 0;
int[] result = new int[a.length - k + 1];
/**
* Create a Double Ended Queue, Qi that will store indexes of array elements
* The queue will store indexes of useful elements in every window and it will
* maintain decreasing order of values from front to rear in Qi, i.e,
* arr[Qi.front[]] to arr[Qi.rear()] are sorted in decreasing order.
*/
ArrayDeque<Integer> deque = new ArrayDeque<>();
for (i = 0; i < k; i++) {
// remove smaller elements on left side of current element
while (!deque.isEmpty() && a[i] > a[deque.peekLast()]) {
deque.removeLast();
}
deque.addLast(i);
}
for (; i < a.length; i++) {
result[j++] = a[deque.peekFirst()];
// remove elements that are outside window k
while (!deque.isEmpty() && deque.peekFirst() <= i - k) {
deque.removeFirst();
}
// remove smaller elements on left side of current element
while (!deque.isEmpty() && a[i] > a[deque.peekLast()]) {
deque.removeLast();
}
deque.addLast(i);
}
// for max in last k elements
result[j] = a[deque.peekFirst()];
return result;
}