โปรแกรมหาค่าสูงสุดของแต่ละสับลิสต์ขนาด K ใน Python

ได้รับลิสต์ nums และ k หา ค่าสูงสุดของทุก subarray (contiguous) ขนาด k

ตัวอย่าง

Input: nums = [12, 7, 3, 9, 10, 9], k = 3

Output: [12, 9, 10, 10]

Windows: [12,7,3]→12, [7,3,9]→9, [3,9,10]→10, [9,10,9]→10

แนวทางแก้ปัญหา

Sliding Window Maximum (Monotonic Deque) - O(N):

1. Deque เก็บ index โดยค่าตรง index นั้น ลดลง (front = max)
2. สำหรับแต่ละ i:
   • Pop front ถ้าออกนอก window (idx ≤ i-k)
   • Pop back ถ้า nums[idx] ≤ nums[i] (maintain decreasing)
   • Push i
   • ถ้า i ≥ k-1 → nums[deque[0]] คือ max ของ window

การใช้งาน (Python - Monotonic Deque)

from collections import deque

class Solution:
    def solve(self, nums, k):
        if k > len(nums) or k <= 0:
            return []
        
        dq = deque()  # store indices
        res = []
        
        for i, x in enumerate(nums):
            # Remove indices out of window
            while dq and dq[0] <= i - k:
                dq.popleft()
            
            # Maintain decreasing order
            while dq and nums[dq[-1]] <= x:
                dq.pop()
            
            dq.append(i)
            
            if i >= k - 1:
                res.append(nums[dq[0]])
        
        return res

# ทดสอบ
ob = Solution()
print(ob.solve([12, 7, 3, 9, 10, 9], 3))  # Output: [12, 9, 10, 10]

วิธีต้นฉบับ (O(N×K) - ช้ากว่า)

โค้ดต้นฉบับใช้การสแกนหา max ใหม่ทุกครั้งที่ max เก่าออกจาก window → worst case O(N×K)

ความซับซ้อน

• Monotonic Deque: O(N) time, O(K) space
• Naive: O(N×K) time