Data structure itself. We don't store the data itself - only max.
class MaxQueue {
deque< pair<int,size_t> > dq; // first is value, second is how many
// time this value is used beside itself
// for example, for [7,3,4,5] 5 will be used 2 times, 7 0 times
public:
void push(int x) {
size_t cnt = 0;
while (!dq.empty() && dq.back().first < x) {
cnt += dq.back().second + 1;
dq.pop_back();
}
dq.emplace_back(x, cnt);
}
void pop() {
if (dq.front().second > 0)
--dq.front().second;
else
dq.pop_front();
}
int max() {
return dq.front().first;
}
};Find max in all windows of length k:
// solution 3. Based on maxqueue
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
if (nums.size() == 0 || k == 0) return {};
MaxQueue mq;
for (int i = 0; i < k-1; ++i)
mq.push(nums[i]);
vector<int> res;
res.reserve(nums.size() - k + 1);
for (int i = k-1; i < nums.size(); ++i) {
mq.push(nums[i]);
res.push_back( mq.max() );
mq.pop();
}
//res.push_back( mq.max() );
return res;
}