Problem solved

The window can only slide right boundary or left boundary to the right, and the left boundary is smaller than the right boundary, maintain the structure of rapid updating of the maximum or minimum value inside the window.

Principle of window update structure

The function is implemented with a double – ended queue.

LinkedList<Integer> qmax = new LinkedList<>(); // Double-endian queueCopy the code

/////////////////////////////////////////////////////////////////////////////////////////////////

/////////////////////////////////////////////////////////////////////////////////////////////////

/////////////////////////////////////////////////////////////////////////////////////////////////

Time complexity

Time complexity: Each position has at most one entry and at most one exit, so the total cost of the update of the double-ended queue must be O(N), and the average cost of a single update is O(N)/N, namely O(1).

The code structure

public static class WindowMax{ private int L; private int R; private int[] arr; Private LinkedList<Integer> qmax; Public WindowMax(int[] a){arr = a; L = -1; R = 0; qmax = new LinkedList<>(); Public void addNumFromRight(){if (R == arr.length){return;} public void addNumFromRight(){if (R == arr. } // The value at the end of the non-empty queue is smaller than the value to be added. qmax.isEmpty() && arr[qmax.peekLast()] <= arr[R]){ qmax.pollLast(); } // add qmax.addLast(R); R++; } public void removeNumFromLeft(){if (L >= r-1){return; } L++; If (qmax.peekFirst() == L){qmax.pollFirst(); Public Integer getMax(){if (! qmax.isEmpty()){ return arr[qmax.peekFirst()]; } return null; }}Copy the code

Related topics

There is an integer array arr and a window of size W that slides from the left to the right, one position at a time (L and R moving simultaneously).

For example, if the array is [4,3,5,4,3,3,6,7] and the window size is 3:

[4 3 5]4 3 3 6 7 The maximum value is 5

4[3 5 4]3 3 6 7 The maximum value in the window is 5

4 3[5 4 3]3 6 7 The maximum value in the window is 5

4 3 5[4 3 3]6 7 The maximum value in the window is 4

4 3 5 4[3 3 6]7 The maximum value in the window is 6

The maximum value in window 4, 3, 5, 4, 3[3, 6, 7] is 7

Please implement a function. Input: integer array arr, window size w.

Output: an array res of length n-w+1, res[I] for each window state. In this case, the result should return {5,5,5,4,6,7}.

Thought analysis

The method used is the structure above, this window is to let R move one step to the right, at the same time let L move one step to the right expire

The relevant code

1- Dual – ended queue

With i-W and timely pop-up window fixed, experience this method, many problems will use

Time complexity O(n)

// This code does not intentionally use L or R. Fixed Windows with i-W and pop-up in time, Public static int[] getMaxWindow(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(); } // Add the address qmax.addlast (I); // I + 1 is the left edge of the window, so I + 1 is the left edge of the window, so I + 1 is the left edge of the window. If (qmax.peekFirst() == i-w){qmax.peekFirst(); } // The critical point indicates that the sliding window has been filled with w [4, 3, 5], I is 2, w is 3, so I + 1 = w // if I is greater than this value, it can be stored in the maximum array, I represents arr[2], If (I >= w-1){arr[] res[index++] = arr[qmax.peekfirst ()]; } } return res; } public static void printArray(int[] arr) { for (int i = 0; i ! = arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); } public static void main(String[] args) { int[] arr = { 4, 3, 5, 4, 3, 3, 6, 7 }; int w = 3; printArray(getMaxWindow(arr, w)); }Copy the code
2- Priority queue (heap)

Time complexity O(nlogn)

class Solution { public int[] maxSlidingWindow(int[] nums, int k) { int n = nums.length; PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() { public int compare(int[] pair1, Int [] pair2) {return pair1[0]! = pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1]; }}); for (int i = 0; i < k; ++i) { pq.offer(new int[]{nums[i], i}); } int[] ans = new int[n - k + 1]; ans[0] = pq.peek()[0]; for (int i = k; i < n; ++i) { pq.offer(new int[]{nums[i], i}); While (pq.peek()[1] <= i-k) {pq.poll(); } ans[i - k + 1] = pq.peek()[0]; } return ans; }}Copy the code

For more information

Leetcode questions 239

Leetcode questions 220