#include <vector>
#include <deque>
#include <iostream>
std::vector<int> maxSlidingWindow(std::vector<int>& nums, int k) {
std::vector<int> result;
std::deque<int> dq;
if (nums.empty()) return result; // Handle the case when nums is empty
for (int i = 0; i < nums.size(); ++i) {
while (!dq.empty() && dq.front() <= i - k) {
dq.pop_front();
}
while (!dq.empty() && nums[dq.back()] <= nums[i]) {
dq.pop_back();
}
dq.push_back(i);
if (i >= k - 1) {
result.push_back(nums[dq.front()]);
}
}
return result;
}
int main() {
std::vector<int> nums1 = {1,3,-1,-3,5,3,6,7};
int k1 = 3;
std::vector<int> result1 = maxSlidingWindow(nums1, k1);
std::cout << "Output for Example 1: ";
for (int num : result1) {
std::cout << num << " ";
}
std::cout << std::endl;
std::vector<int> nums2 = {1};
int k2 = 1;
std::vector<int> result2 = maxSlidingWindow(nums2, k2);
std::cout << "Output for Example 2: ";
for (int num : result2) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
I2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPGRlcXVlPgojaW5jbHVkZSA8aW9zdHJlYW0+CgpzdGQ6OnZlY3RvcjxpbnQ+IG1heFNsaWRpbmdXaW5kb3coc3RkOjp2ZWN0b3I8aW50PiYgbnVtcywgaW50IGspIHsKICAgIHN0ZDo6dmVjdG9yPGludD4gcmVzdWx0OwogICAgc3RkOjpkZXF1ZTxpbnQ+IGRxOwoKICAgIGlmIChudW1zLmVtcHR5KCkpIHJldHVybiByZXN1bHQ7IC8vIEhhbmRsZSB0aGUgY2FzZSB3aGVuIG51bXMgaXMgZW1wdHkKCiAgICBmb3IgKGludCBpID0gMDsgaSA8IG51bXMuc2l6ZSgpOyArK2kpIHsKICAgICAgICB3aGlsZSAoIWRxLmVtcHR5KCkgJiYgZHEuZnJvbnQoKSA8PSBpIC0gaykgewogICAgICAgICAgICBkcS5wb3BfZnJvbnQoKTsKICAgICAgICB9CiAgICAgICAgCiAgICAgICAgd2hpbGUgKCFkcS5lbXB0eSgpICYmIG51bXNbZHEuYmFjaygpXSA8PSBudW1zW2ldKSB7CiAgICAgICAgICAgIGRxLnBvcF9iYWNrKCk7CiAgICAgICAgfQogICAgICAgIAogICAgICAgIGRxLnB1c2hfYmFjayhpKTsKICAgICAgICAKICAgICAgICBpZiAoaSA+PSBrIC0gMSkgewogICAgICAgICAgICByZXN1bHQucHVzaF9iYWNrKG51bXNbZHEuZnJvbnQoKV0pOwogICAgICAgIH0KICAgIH0KCiAgICByZXR1cm4gcmVzdWx0Owp9CgppbnQgbWFpbigpIHsKICAgIHN0ZDo6dmVjdG9yPGludD4gbnVtczEgPSB7MSwzLC0xLC0zLDUsMyw2LDd9OwogICAgaW50IGsxID0gMzsKICAgIHN0ZDo6dmVjdG9yPGludD4gcmVzdWx0MSA9IG1heFNsaWRpbmdXaW5kb3cobnVtczEsIGsxKTsKICAgIHN0ZDo6Y291dCA8PCAiT3V0cHV0IGZvciBFeGFtcGxlIDE6ICI7CiAgICBmb3IgKGludCBudW0gOiByZXN1bHQxKSB7CiAgICAgICAgc3RkOjpjb3V0IDw8IG51bSA8PCAiICI7CiAgICB9CiAgICBzdGQ6OmNvdXQgPDwgc3RkOjplbmRsOwoKICAgIHN0ZDo6dmVjdG9yPGludD4gbnVtczIgPSB7MX07CiAgICBpbnQgazIgPSAxOwogICAgc3RkOjp2ZWN0b3I8aW50PiByZXN1bHQyID0gbWF4U2xpZGluZ1dpbmRvdyhudW1zMiwgazIpOwogICAgc3RkOjpjb3V0IDw8ICJPdXRwdXQgZm9yIEV4YW1wbGUgMjogIjsKICAgIGZvciAoaW50IG51bSA6IHJlc3VsdDIpIHsKICAgICAgICBzdGQ6OmNvdXQgPDwgbnVtIDw8ICIgIjsKICAgIH0KICAgIHN0ZDo6Y291dCA8PCBzdGQ6OmVuZGw7CgogICAgcmV0dXJuIDA7Cn0K