#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) {
// Remove indices from the front of the deque if they are outside the current window
while (!dq.empty() && dq.front() <= i - k) {
dq.pop_front();
}
// Remove indices from the back of the deque if the corresponding elements in nums are smaller than or equal to nums[i]
while (!dq.empty() && nums[dq.back()] <= nums[i]) {
dq.pop_back();
}
dq.push_back(i);
// Add the maximum element to the result when the window size reaches k
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+IGRxOwoKICAgIGlmIChudW1zLmVtcHR5KCkpIHJldHVybiByZXN1bHQ7IC8vIEhhbmRsZSB0aGUgY2FzZSB3aGVuIG51bXMgaXMgZW1wdHkKCiAgICBmb3IgKGludCBpID0gMDsgaSA8IG51bXMuc2l6ZSgpOyArK2kpIHsKICAgICAgICAvLyBSZW1vdmUgaW5kaWNlcyBmcm9tIHRoZSBmcm9udCBvZiB0aGUgZGVxdWUgaWYgdGhleSBhcmUgb3V0c2lkZSB0aGUgY3VycmVudCB3aW5kb3cKICAgICAgICB3aGlsZSAoIWRxLmVtcHR5KCkgJiYgZHEuZnJvbnQoKSA8PSBpIC0gaykgewogICAgICAgICAgICBkcS5wb3BfZnJvbnQoKTsKICAgICAgICB9CiAgICAgICAgCiAgICAgICAgLy8gUmVtb3ZlIGluZGljZXMgZnJvbSB0aGUgYmFjayBvZiB0aGUgZGVxdWUgaWYgdGhlIGNvcnJlc3BvbmRpbmcgZWxlbWVudHMgaW4gbnVtcyBhcmUgc21hbGxlciB0aGFuIG9yIGVxdWFsIHRvIG51bXNbaV0KICAgICAgICB3aGlsZSAoIWRxLmVtcHR5KCkgJiYgbnVtc1tkcS5iYWNrKCldIDw9IG51bXNbaV0pIHsKICAgICAgICAgICAgZHEucG9wX2JhY2soKTsKICAgICAgICB9CiAgICAgICAgCiAgICAgICAgZHEucHVzaF9iYWNrKGkpOwogICAgICAgIAogICAgICAgIC8vIEFkZCB0aGUgbWF4aW11bSBlbGVtZW50IHRvIHRoZSByZXN1bHQgd2hlbiB0aGUgd2luZG93IHNpemUgcmVhY2hlcyBrCiAgICAgICAgaWYgKGkgPj0gayAtIDEpIHsKICAgICAgICAgICAgcmVzdWx0LnB1c2hfYmFjayhudW1zW2RxLmZyb250KCldKTsKICAgICAgICB9CiAgICB9CgogICAgcmV0dXJuIHJlc3VsdDsKfQoKaW50IG1haW4oKSB7CiAgICBzdGQ6OnZlY3RvcjxpbnQ+IG51bXMxID0gezEsMywtMSwtMyw1LDMsNiw3fTsKICAgIGludCBrMSA9IDM7CiAgICBzdGQ6OnZlY3RvcjxpbnQ+IHJlc3VsdDEgPSBtYXhTbGlkaW5nV2luZG93KG51bXMxLCBrMSk7CiAgICBzdGQ6OmNvdXQgPDwgIk91dHB1dCBmb3IgRXhhbXBsZSAxOiAiOwogICAgZm9yIChpbnQgbnVtIDogcmVzdWx0MSkgewogICAgICAgIHN0ZDo6Y291dCA8PCBudW0gPDwgIiAiOwogICAgfQogICAgc3RkOjpjb3V0IDw8IHN0ZDo6ZW5kbDsKCiAgICBzdGQ6OnZlY3RvcjxpbnQ+IG51bXMyID0gezF9OwogICAgaW50IGsyID0gMTsKICAgIHN0ZDo6dmVjdG9yPGludD4gcmVzdWx0MiA9IG1heFNsaWRpbmdXaW5kb3cobnVtczIsIGsyKTsKICAgIHN0ZDo6Y291dCA8PCAiT3V0cHV0IGZvciBFeGFtcGxlIDI6ICI7CiAgICBmb3IgKGludCBudW0gOiByZXN1bHQyKSB7CiAgICAgICAgc3RkOjpjb3V0IDw8IG51bSA8PCAiICI7CiAgICB9CiAgICBzdGQ6OmNvdXQgPDwgc3RkOjplbmRsOwoKICAgIHJldHVybiAwOwp9Cg==