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]
Example 3:
Input: nums = [1,-1], k = 1 Output: [1,-1]
Example 4:
Input: nums = [9,11], k = 2 Output: [11]
Example 5:
Input: nums = [4,-2], k = 2 Output: [4]
Constraints:
1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length
A:
首先,用了一个monotonous decreasing vector , say V, 来记录每次windows里从大到小的值。
每次加入一个新值,则V 最后的一定要比前面的都小,否则,如果大,就可以pop出来
然后,每次需要删除前面的值。 而被删除的值, 只有等于 V的第一个值的时候,才可能是存在V里的。(那个时候,为了不删除,我们直接前进一个index即可)
**************第二遍,用std::deque
, 方便前后删*******
class Solution { public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { vector<int> res; deque<int> DQ; for(int i =0;i<nums.size();i++){ if(i>=k && nums[i-k]>=DQ.front()){ DQ.pop_front(); } while(not DQ.empty() && DQ.back() < nums[i]){ DQ.pop_back(); } DQ.push_back(nums[i]); if(i>=k-1){ res.push_back(DQ.front());} } return res; } };
Amortized analysis 复杂度是: O(n).
虽然感觉while loop.然后,每个数字,最多被push 一次, 也最多被pop一次。
No comments:
Post a Comment