Sliding Window Maximum
Problem statement:
Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.
Window position Max --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7
Therefore, return the max sliding window as [3,3,5,5,6,7].
Note:
You may assume k is always valid, ie: 1 ≤ k ≤ input array's size for non-empty array.
Follow up:
Could you solve it in linear time?
A first glance maybe we can solve this by using a max heap ordered by the value of the element, but we have to keep in mind one thing: the order of popping elements is not by value, it's by its actual index, and if we have a tie in value, we need to keep track all possible indices it occurs and only pop out this element when its possible indices reaches zero. This is somewhat laborous to maintain such a heap.
In fact for the problem, we only need to know the maximum of this window and the order of popping element out of the window is by its index in original array. So this should be a max heap problem instead of max heap.
Here's how to maintain the window:
We keep updating elements of current window in a stack, and as we move right the window by one each time, we update the max value. To make sure pop_front and push_back are efficient we can use a deque.
The key question here is how can we keep track of the maximum inside the window? We can easily do a O(k) search every time but this will run into O(kn) time complexity. Actually we can do better by discard those which is both indexed before current maximum and has a value less then the current maximum.
By doing so we can have better average runtime complexity, best case O(n) if original array is ascending, but can be as worst as O(nk) if original array is descending. But on array it will run in O(n) with a much smaller constant factor than k.
Here's the illustration of how we keep the window:
[1 2 3 4] 5 3 2 4 1
Current window: [4]
Next window before search: [4, 5]
Next window after search: [5]
Suppose we have window size of 4 and current window covers [1 2 3 4], in our current window we only keep [4] because popping [1, 2, 3] doesn't affect the maximum element. Once we push in 5, we will update the current maximum since the new element is bigger than old top.
1 2 3 4 [5 3 2 4] 1
Current window: [5 3 2 4]
Next window before search : [3, 2, 4, 1]
Next window after search: [4, 1]
Now with the same array, suppose we are covering [5, 4, 3, 2] this time. The next element is [1] and we are going to pop [5]. Since we are removing the current top, we need to do a search again for the new top and discard whatever is before this new top. And of course our new top will be [4] and whatever is before it will be discarded and newly pushed [1] will be added to it.
Code implementation as follows:
(Note: You can use deque or vector, it's gonna be similar in performance. If you use deque, do popping when discarding elements before the top, if you use vector, clear the vector and pushing everything after the new top as well as the top)
Note:
You may assume k is always valid, ie: 1 ≤ k ≤ input array's size for non-empty array.
Follow up:
Could you solve it in linear time?
Solution: Max stack based solution.
A first glance maybe we can solve this by using a max heap ordered by the value of the element, but we have to keep in mind one thing: the order of popping elements is not by value, it's by its actual index, and if we have a tie in value, we need to keep track all possible indices it occurs and only pop out this element when its possible indices reaches zero. This is somewhat laborous to maintain such a heap.
In fact for the problem, we only need to know the maximum of this window and the order of popping element out of the window is by its index in original array. So this should be a max heap problem instead of max heap.
Here's how to maintain the window:
We keep updating elements of current window in a stack, and as we move right the window by one each time, we update the max value. To make sure pop_front and push_back are efficient we can use a deque.
The key question here is how can we keep track of the maximum inside the window? We can easily do a O(k) search every time but this will run into O(kn) time complexity. Actually we can do better by discard those which is both indexed before current maximum and has a value less then the current maximum.
By doing so we can have better average runtime complexity, best case O(n) if original array is ascending, but can be as worst as O(nk) if original array is descending. But on array it will run in O(n) with a much smaller constant factor than k.
Here's the illustration of how we keep the window:
[1 2 3 4] 5 3 2 4 1
Current window: [4]
Next window before search: [4, 5]
Next window after search: [5]
Suppose we have window size of 4 and current window covers [1 2 3 4], in our current window we only keep [4] because popping [1, 2, 3] doesn't affect the maximum element. Once we push in 5, we will update the current maximum since the new element is bigger than old top.
1 2 3 4 [5 3 2 4] 1
Current window: [5 3 2 4]
Next window before search : [3, 2, 4, 1]
Next window after search: [4, 1]
Now with the same array, suppose we are covering [5, 4, 3, 2] this time. The next element is [1] and we are going to pop [5]. Since we are removing the current top, we need to do a search again for the new top and discard whatever is before this new top. And of course our new top will be [4] and whatever is before it will be discarded and newly pushed [1] will be added to it.
Code implementation as follows:
(Note: You can use deque or vector, it's gonna be similar in performance. If you use deque, do popping when discarding elements before the top, if you use vector, clear the vector and pushing everything after the new top as well as the top)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | class Solution { public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { vector<int> results; if (nums.empty()) return results; /* initialize window */ vector<int> candidates; initCandidates(nums, candidates, 0, k-1); for (int lhs=0, rhs=k-1; rhs < nums.size(); lhs++, rhs++) { results.push_back(nums[candidates[0]]); if (rhs+1 < nums.size()) { if (nums[rhs+1] > nums[candidates[0]]) { candidates.clear(); candidates.push_back(rhs+1); continue; } else { candidates.push_back(nums[rhs+1]); if (lhs == candidates[0]) { initCandidates(nums, candidates, lhs+1, rhs+1); } } } } return results; } inline void initCandidates(const vector<int>& nums, vector<int>& candidates, int lhs, int rhs) { int max_idx = lhs; for (int j=lhs+1; j<=rhs; j++) { if (nums[j] > nums[max_idx]) { max_idx = j; } } candidates.clear(); for (int j=max_idx; j<=rhs; j++) candidates.push_back(j); } }; |
No comments:
Post a Comment