239. Sliding Window Maximum | LeetCode
You are given an array of integers 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.
Return the max sliding window.
Example 1:
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3 Output: [3,3,5,5,6,7] Explanation: 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
Example 2:
Input: nums = [1], k = 1 Output: [1]
Constraints:
1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length
Solution:
class Solution {public:vector<int> maxSlidingWindow(vector<int>& v, int k) {vector<int>ans;for(int i=0; i<=v.size()-k; i++){int temp=INT_MIN;for(int j=i; j<i+k && j<v.size(); j++)temp=max(temp,v[j]);ans.push_back(temp);}return ans;}};
So how can we optimize this solution? Heard of Deque we can use that here. In deque, we can insert and pop from both back and front. We will keep a deque and the maximum elements in that. At first, we will check whether the maximum element ( from front) belong to the current window or not if not we will pop until we get the maximum element in the current window of size k.
Now we will check from the back if the current element is greater than the element in the back of deque if yes we will pop until we find a greater element in the back of deque. We will then insert the current element in the back of deque and the front of deque will be the maximum element in the window of size k.
sdf
0 Comments
If you have any doubts/suggestion/any query or want to improve this article, you can comment down below and let me know. Will reply to you soon.