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;

Challenge

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;

}

};

results matching ""

    No results matching ""