Chương trình tìm giá trị lớn nhất của các mảng con kích thước k trong Python

Cho mảng nums và số k. Tìm giá trị lớn nhất của mỗi mảng con liên tiếp kích thước k (sliding window maximum).

Ví dụ: nums=[12,7,3,9,10,9], k=3 → [12, 9, 10, 10].

Giải thuật (Tối ưu theo dõi max và vị trí - Không dùng Deque)

1. Tìm max của cửa sổ đầu tiên [0..k-1], lưu giá trị temp và vị trí point.
2. Duyệt i từ k đến n-1:
   • Nếu nums[i] < temp và i - point < k: max cũ vẫn trong cửa sổ → giữ nguyên.
   • Nếu nums[i] < temp và i - point >= k: max cũ ra khỏi cửa sổ → quét lại cửa sổ [i-k+1, i] tìm max mới.
   • Nếu nums[i] >= temp: max mới là nums[i], cập nhật point = i.

Lưu ý: Cách này trung bình O(n) nhưng worst-case O(n*k) khi max liên tục ra khỏi cửa sổ. Cách chuẩn O(n) dùng Deque đơn điệu.

Ví dụ minh họa

class Solution:
    def solve(self, nums, k):
        if k > len(nums):
            return []
        res = []
        temp = nums[0]
        point = 0
        for i in range(k):
            if nums[i] > temp:
                temp = nums[i]
                point = i
        res.append(temp)
        
        for i in range(k, len(nums)):
            if nums[i] < temp and (i - point) < k:
                temp = nums[point]
            elif nums[i] < temp and (i - point) >= k:
                point = i - k + 1
                for j in range(i - k + 1, i + 1):
                    if nums[j] > nums[point]:
                        point = j
                temp = nums[point]
            else:
                temp = nums[i]
                point = i
            res.append(temp)
        return res

ob = Solution()
nums = [12, 7, 3, 9, 10, 9]
k = 3
print(ob.solve(nums, k))  # Output: [12, 9, 10, 10]

Đầu vào / Đầu ra

Input: [12, 7, 3, 9, 10, 9], 3

Output: [12, 9, 10, 10]