#include <iostream>
#include <vector>
#include <deque>
std::vector<int> maxSlidingWindow(std::vector<int>& nums, int k) {
std::vector<int> result;
std::deque<int> window;
for (int i = 0; i < nums.size(); ++i) {
// Remove elements outside of the window
if (!window.empty() && window.front() == i - k)
window.pop_front();
// Remove elements smaller than the current number
while (!window.empty() && nums[i] >= nums[window.back()])
window.pop_back();
// Add current number to the window
window.push_back(i);
// If the window is at least of size k, add the maximum element to the result
if (i >= k - 1)
result.push_back(nums[window.front()]);
}
return result;
}
int main() {
std::vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
std::vector<int> result = maxSlidingWindow(nums, k);
std::cout << "Maximum sliding window: ";
for (int num : result)
std::cout << num << " ";
std::cout << std::endl;
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8ZGVxdWU+CgpzdGQ6OnZlY3RvcjxpbnQ+IG1heFNsaWRpbmdXaW5kb3coc3RkOjp2ZWN0b3I8aW50PiYgbnVtcywgaW50IGspIHsKICAgIHN0ZDo6dmVjdG9yPGludD4gcmVzdWx0OwogICAgc3RkOjpkZXF1ZTxpbnQ+IHdpbmRvdzsKCiAgICBmb3IgKGludCBpID0gMDsgaSA8IG51bXMuc2l6ZSgpOyArK2kpIHsKICAgICAgICAvLyBSZW1vdmUgZWxlbWVudHMgb3V0c2lkZSBvZiB0aGUgd2luZG93CiAgICAgICAgaWYgKCF3aW5kb3cuZW1wdHkoKSAmJiB3aW5kb3cuZnJvbnQoKSA9PSBpIC0gaykKICAgICAgICAgICAgd2luZG93LnBvcF9mcm9udCgpOwogICAgICAgIAogICAgICAgIC8vIFJlbW92ZSBlbGVtZW50cyBzbWFsbGVyIHRoYW4gdGhlIGN1cnJlbnQgbnVtYmVyCiAgICAgICAgd2hpbGUgKCF3aW5kb3cuZW1wdHkoKSAmJiBudW1zW2ldID49IG51bXNbd2luZG93LmJhY2soKV0pCiAgICAgICAgICAgIHdpbmRvdy5wb3BfYmFjaygpOwogICAgICAgIAogICAgICAgIC8vIEFkZCBjdXJyZW50IG51bWJlciB0byB0aGUgd2luZG93CiAgICAgICAgd2luZG93LnB1c2hfYmFjayhpKTsKICAgICAgICAKICAgICAgICAvLyBJZiB0aGUgd2luZG93IGlzIGF0IGxlYXN0IG9mIHNpemUgaywgYWRkIHRoZSBtYXhpbXVtIGVsZW1lbnQgdG8gdGhlIHJlc3VsdAogICAgICAgIGlmIChpID49IGsgLSAxKQogICAgICAgICAgICByZXN1bHQucHVzaF9iYWNrKG51bXNbd2luZG93LmZyb250KCldKTsKICAgIH0KICAgIAogICAgcmV0dXJuIHJlc3VsdDsKfQoKaW50IG1haW4oKSB7CiAgICBzdGQ6OnZlY3RvcjxpbnQ+IG51bXMgPSB7MSwgMywgLTEsIC0zLCA1LCAzLCA2LCA3fTsKICAgIGludCBrID0gMzsKICAgIHN0ZDo6dmVjdG9yPGludD4gcmVzdWx0ID0gbWF4U2xpZGluZ1dpbmRvdyhudW1zLCBrKTsKCiAgICBzdGQ6OmNvdXQgPDwgIk1heGltdW0gc2xpZGluZyB3aW5kb3c6ICI7CiAgICBmb3IgKGludCBudW0gOiByZXN1bHQpCiAgICAgICAgc3RkOjpjb3V0IDw8IG51bSA8PCAiICI7CiAgICBzdGQ6OmNvdXQgPDwgc3RkOjplbmRsOwoKICAgIHJldHVybiAwOwp9Cg==