DataStructure/239. Sliding Window Maximum.cpp at main · Kunalgithub24/DataStructure · GitHub

25 lines (21 loc) · 679 Bytes

class Solution {

public:

vector<int> maxSlidingWindow(vector<int>& nums, int k) {

int n = nums.size();

vector<int> ans;

deque<int> dq;

for (int i = 0; i < n; i++) {

// Remove indices outside the window

if (!dq.empty() && dq.front() <= i - k)

dq.pop_front();

// Maintain decreasing order in deque

while (!dq.empty() && nums[dq.back()] <= nums[i])

dq.pop_back();

dq.push_back(i);

// Add maximum for the current window

if (i >= k - 1)

ans.push_back(nums[dq.front()]);

}

return ans;

}

};

Expand file tree