This is the 31st day of my participation in the August More Text Challenge

Refer to Offer 59-i. Maximum sliding window

The title

Given an array nums and the size k of the sliding window, find the maximum number of sliding Windows.

Example:

Input: nums = [1, 3, 1, 3,5,3,6,7], and k = 3 output:,3,5,5,6,7 [3] : The position of the sliding window Maximum -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- [1] 3-1-3 3 5 6 7 3 1 [3-1-3] 3 5 6 7 3 1 3 [1-3-5] 3 6 7 5 3-1/3-3 5 6 7 5 1 3 1-3 [5 3 6] 7 6 1 3 1-3 5 [3 6 7] 7Copy the code

Tip:

You can assume that k is always valid, 1 ≤ k ≤ the size of the input array if the input array is not empty.

Methods a

Sliding window template: maintains a queue in which the value of the element in the current window is the maximum value in the window; Each time you swipe backwards, determine whether the right element has slid out of the window. Each time an element is added to the queue, an element smaller than the current element is added to the end of the queue.

class Solution { public int[] maxSlidingWindow(int[] nums, int k) { int n = nums.length, idx = 0; if (n == 0) return new int[0]; int[] res = new int[n - k + 1]; LinkedList<Integer> q = new LinkedList<>(); for (int i = 0; i < n; i ++ ) { if (q.size() > 0 && i - k >= q.getFirst()) q.poll(); while(q.size() > 0 && nums[i] >= nums[q.getLast()]) q.removeLast(); q.addLast(i); if (i >= k - 1) res[idx ++] = nums[q.getFirst()]; } return res; }}Copy the code

Time complexity: O(n)

Space complexity: O(k)

Refer to Offer 59-II. Maximum number of queues

The title

Define a queue and implement the max_value function to get the maximum value in the queue, requiring the amortized time complexity of max_value, push_back, and pop_front to be O(1).

If the queue is empty, pop_front and max_value must return -1

Example 1:

Input: [" MaxQueue ", "push_back push_back", "max_value", "pop_front", "max_value"] [[], [1], [2], [], [], []] output: 2,1,2] [null, null, null,Copy the code

Example 2:

Input: [" MaxQueue pop_front ", ""," max_value "] [[], [], []] output: (null, 1, 1)Copy the code

Limitations:

  • 1 <= push_back,pop_front,max_value total operands <= 10000
  • 1 <= value <= 10^5

Methods a

Maintain a double-ended queue D to record the maximum value in the queue

  • Pop up every time you add an elementdIs smaller than the tail element of the newly added value
  • Determine when an element is deleteddIs the element equal to the same element in the. If so, delete it;
class MaxQueue { LinkedList<Integer> q1, q2; public MaxQueue() { q1 = new LinkedList<>(); q2 = new LinkedList<>(); } public int max_value() { if (q2.size() == 0) return -1; return q2.getFirst(); } public void push_back(int value) { q1.add(value); while(q2.size() > 0 && q2.getLast() < value) q2.removeLast(); q2.add(value); } public int pop_front() { if (q1.size() == 0) return -1; int t = q1.poll(); if (q2.getFirst() == t) q2.poll(); return t; } } /** * Your MaxQueue object will be instantiated and called as such: * MaxQueue obj = new MaxQueue(); * int param_1 = obj.max_value(); * obj.push_back(value); * int param_3 = obj.pop_front(); * /Copy the code