#include <iostream>
#include <vector>
#include <deque>
using namespace std;
vector<int> maxSlidingWindow(std::vector<int>& nums, int k) {
vector<int> result;
deque<int> window;
for (int i = 0; i < nums.size(); ++i) {
if (!window.empty() && window.front() == i - k)
window.pop_front();
while (!window.empty() && nums[i] >= nums[window.back()])
window.pop_back();
window.push_back(i);
if (i >= k - 1)
result.push_back(nums[window.front()]);
}
return result;
}
int main() {
vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
vector<int> result = maxSlidingWindow(nums, k);
cout << "Maximum sliding window: ";
for (int num : result)
cout << num << " ";
cout << endl;
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8ZGVxdWU+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKdmVjdG9yPGludD4gbWF4U2xpZGluZ1dpbmRvdyhzdGQ6OnZlY3RvcjxpbnQ+JiBudW1zLCBpbnQgaykgewogICAgdmVjdG9yPGludD4gcmVzdWx0OwogICAgZGVxdWU8aW50PiB3aW5kb3c7CgogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBudW1zLnNpemUoKTsgKytpKSB7CiAgICAgICAgaWYgKCF3aW5kb3cuZW1wdHkoKSAmJiB3aW5kb3cuZnJvbnQoKSA9PSBpIC0gaykKICAgICAgICAgICAgd2luZG93LnBvcF9mcm9udCgpOwoKICAgICAgICB3aGlsZSAoIXdpbmRvdy5lbXB0eSgpICYmIG51bXNbaV0gPj0gbnVtc1t3aW5kb3cuYmFjaygpXSkKICAgICAgICAgICAgd2luZG93LnBvcF9iYWNrKCk7CgogICAgICAgIHdpbmRvdy5wdXNoX2JhY2soaSk7CgogICAgICAgIGlmIChpID49IGsgLSAxKQogICAgICAgICAgICByZXN1bHQucHVzaF9iYWNrKG51bXNbd2luZG93LmZyb250KCldKTsKICAgIH0KCiAgICByZXR1cm4gcmVzdWx0Owp9CgppbnQgbWFpbigpIHsKICAgIHZlY3RvcjxpbnQ+IG51bXMgPSB7MSwgMywgLTEsIC0zLCA1LCAzLCA2LCA3fTsKICAgIGludCBrID0gMzsKICAgIHZlY3RvcjxpbnQ+IHJlc3VsdCA9IG1heFNsaWRpbmdXaW5kb3cobnVtcywgayk7CgogICAgY291dCA8PCAiTWF4aW11bSBzbGlkaW5nIHdpbmRvdzogIjsKICAgIGZvciAoaW50IG51bSA6IHJlc3VsdCkKICAgIGNvdXQgPDwgbnVtIDw8ICIgIjsKICAgIGNvdXQgPDwgZW5kbDsKCiAgICByZXR1cm4gMDsKfQ==