4.4 Sliding Window Maximum (Monotonic Deque)

Demo: Sliding Window Maximum — LC 239 (Hard — Google/Uber High)

Statement (Demo): integer array nums ও integer k দেওয়া — size k-এর প্রতিটা sliding window-এর maximum element বের করুন। উদাহরণ: nums=[1,3,-1,-3,5,3,6,7], k=3 → [3,3,5,5,6,7] | ⚡ n ≤ 10⁵, -10⁴ ≤ nums[i] ≤ 10⁴

Approach: deque-এ index রাখুন যাতে মানগুলো decreasing থাকে — front সবসময় window-এর max। নতুন এলিমেন্টের চেয়ে ছোট সব পেছন থেকে ফেলে দিন (ওরা আর কখনো max হবে না), আর window-এর বাইরে পড়া front ফেলে দিন।

function maxSlidingWindow(nums, k) {
  const deque = []; // index, মান decreasing
  const res = [];
  for (let i = 0; i < nums.length; i++) {
    if (deque.length && deque[0] <= i - k) deque.shift(); // window-এর বাইরে
    while (deque.length && nums[deque[deque.length - 1]] <= nums[i])
      deque.pop();
    deque.push(i);
    if (i >= k - 1) res.push(nums[deque[0]]);
  }
  return res;
}

Complexity: Time O(n), Space O(k) (নোট: JS-এ shift() O(n) — বড় input-এ head pointer ব্যবহার করুন)