ค่าสูงสุดแบบหน้าต่างเลื่อนใน C++ (Sliding Window Maximum)

ภาพรวมปัญหา

ให้อาเรย์ nums และขนาดหน้าต่าง k หาค่าสูงสุดในแต่ละหน้าต่างที่เลื่อนทีละ 1

ตัวอย่าง

nums = [1,3,-1,-3,5,3,6,8], k = 3
Output: [3,3,5,5,6,8]

วิธีแก้ปัญหา: Deque (Monotonic Queue)

เก็บ index ใน deque เรียงตามค่า nums จากมากไปน้อย
- Front = ค่าสูงสุดของหน้าต่างปัจจุบัน
- Pop back: ขณะ nums[back] < nums[i]
- Pop front: ขณะ front < i-k+1 (ออกนอกหน้าต่าง)

โค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> ans;
        deque<int> dq;
        if (nums.empty()) return ans;
        for (int i = 0; i < k; i++) {
            while (!dq.empty() && nums[dq.back()] < nums[i]) dq.pop_back();
            dq.push_back(i);
        }
        for (int i = k; i < nums.size(); i++) {
            ans.push_back(nums[dq.front()]);
            while (!dq.empty() && dq.front() < i - k + 1) dq.pop_front();
            while (!dq.empty() && nums[dq.back()] < nums[i]) dq.pop_back();
            dq.push_back(i);
        }
        ans.push_back(nums[dq.front()]);
        return ans;
    }
};

int main() {
    Solution ob;
    vector<int> v = {1,3,-1,-3,5,3,6,8};
    // print_vector(ob.maxSlidingWindow(v,3));
}

การวิเคราะห์ความซับซ้อน

• เวลา: O(n) — แต่ละ index push/pop สูงสุด 1 ครั้ง
• พื้นที่: O(k)