sliding window max
vector<int> solve(vector<int>& nums, int k) { vector<int>ans; if(k>nums.size())return ans; deque<int>dq; for(int i = 0; i < k; i++) { while(!dq.empty() && nums[dq.back()]<=nums[i]) { dq.pop_back(); } dq.push_back(i); } ans.push_back(nums[dq.front()]); for(int i = k; i < nums.size(); i++) { if(!dq.empty() && dq.front()<=i-k)dq.pop_front(); while(!dq.empty() && nums[dq.back()]<=nums[i]) { dq.pop_back(); } dq.push_back(i); ans.push_back(nums[dq.front()]); } return ans; }
sliding window maximum
# Python program to find the maximum for # each and every contiguous subarray of # size k from collections import deque # A Deque (Double ended queue) based # method for printing maximum element # of all subarrays of size k def printMax(arr, n, k): """ 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""" Qi = deque() # Process first k (or first window) # elements of array for i in range(k): # For every element, the previous # smaller elements are useless # so remove them from Qi while Qi and arr[i] >= arr[Qi[-1]] : Qi.pop() # Add new element at rear of queue Qi.append(i); # Process rest of the elements, i.e. # from arr[k] to arr[n-1] for i in range(k, n): # The element at the front of the # queue is the largest element of # previous window, so print it print(str(arr[Qi[0]]) + " ", end = "") # Remove the elements which are # out of this window while Qi and Qi[0] <= i-k: # remove from front of deque Qi.popleft() # Remove all elements smaller than # the currently being added element # (Remove useless elements) while Qi and arr[i] >= arr[Qi[-1]] : Qi.pop() # Add current element at the rear of Qi Qi.append(i) # Print the maximum element of last window print(str(arr[Qi[0]])) # Driver code if __name__=="__main__": arr = [12, 1, 78, 90, 57, 89, 56] k = 3 printMax(arr, len(arr), k) # This code is contributed by Shiv Shankar
Source: www.geeksforgeeks.org