Given an array of n integer with duplicate number, and a moving window(size k), move the window at each iteration from the start of the array, find the maximum number inside the window at each moving.
Have you met this question in a real interview?
Yes
Example
For array[1, 2, 7, 7, 8]
, moving window sizek = 3
. return[7, 7, 8]
At first the window is at the start of the array like this
[|1, 2, 7| ,7, 8]
, return the maximum7
;
then the window move one step forward.
[1, |2, 7 ,7|, 8]
, return the maximum7
;
then the window move one step forward again.
[1, 2, |7, 7, 8|]
, return the maximum8
;
o(n) time and O(k) memory
using index to know whether a number is out of window
class Solution {
public:
/\*\*
\* @param nums: A list of integers.
\* @return: The maximum number inside the window at each moving.
\*/
vector<int> maxSlidingWindow\(vector<int> &nums, int k\) {
// write your code here
vector<int> res;
if \(nums.size\(\) < k\) {
return res;
}
deque<int> q;
for \(int i = 0; i < k-1; ++i\) {
while \(!q.empty\(\) && nums\[q.back\(\)\] < nums\[i\]\) {
q.pop\_back\(\);
}
q.push\_back\(i\);
}
for \(int i = k-1; i < nums.size\(\); ++i\) {
if \(q.front\(\) <= i-k\) {
q.pop\_front\(\);
}
while \(!q.empty\(\) && nums\[q.back\(\)\] < nums\[i\]\) {
q.pop\_back\(\);
}
q.push\_back\(i\);
res.push\_back\(nums\[q.front\(\)\]\);
}
return res;
}
};