Approach 1: O(nlogk)
Maintain a multiset which always contains the k elements to be considered. Since sets are ordered in non-decreasing order by default, the last element in this multiset will be our answer at each step. Now, how to maintain only the k elements to be considered in the set? Along with the set, have an array of size k which stores an iterator the element in the set. The first k elements go to array[i..k]. Now, for the (k+1)-th element, we remove the element pointed by array[0] in the set and put the iterator to (k+1)-th element into array[0]. The code below is easy to understand:
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
if (!nums.size())
return {};
multiset<int> set;
vector<multiset<int>::iterator> v(k, set.end());
int count = 0;
vector<int> ans;
for (int i=0; i<nums.size(); i++, count++) {
if (i<k) {
v[count] = set.insert(nums[i]);
} else {
ans.push_back(*set.rbegin());
set.erase(v[count%k]);
v[count%k] = set.insert(nums[i]);
}
}
ans.push_back(*set.rbegin());
return ans;
}
};
Approach 2: O(n) amortized
This is a classical problem solved in amortized O(n) time using Max Queue. I highly recommend reading the article Min stack/queue before proceeding. The below code implements Max Queue which will be evident after an understanding of the Min Queue in the article above.
class Solution {
public:
deque<pair<int,int>> maxQ;
int addCnt = 0;
int removeCnt = 0;
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
if (!nums.size())
return {};
vector<int> res;
for (int i=0; i<nums.size(); i++) {
if (i<k) {
add(nums[i]);
} else {
res.push_back(getMin());
add(nums[i]);
remove();
}
}
res.push_back(getMin());
return res;
}
void add (int val) {
while (!maxQ.empty() && maxQ.back().first<val)
maxQ.pop_back();
maxQ.push_back({val, addCnt});
addCnt++;
}
int getMin () {
return maxQ.front().first;
}
void remove () {
if (!maxQ.empty() && maxQ.front().second == removeCnt)
maxQ.pop_front();
removeCnt++;
}
};