Sliding Window Maximum

Description:

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.

Example

For array [1, 2, 7, 7, 8], moving window size k = 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 maximum 7;

then the window move one step forward.

[1, |2, 7 ,7|, 8], return the maximum 7;

then the window move one step forward again.

[1, 2, |7, 7, 8|], return the maximum 8;

Challenge

o(n) time and O(k) memory

Solution:

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) { vector<int> rc; auto sz = (int)nums.size(); if (k == 0 || sz < k) return rc; deque<int> ids; for (int i = 0; i < sz; ++i) { while (!ids.empty() && nums[ids.back()] < nums[i]) ids.pop_back(); ids.push_back(i); while (ids.front() <= i-k) ids.pop_front(); if (i >= k-1) rc.push_back(nums[ids.front()]); } return rc; } };

转载于:https://www.cnblogs.com/deofly/p/sliding-window-maximum.html

相关资源：JAVA上百实例源码以及开源项目