Bài toán "Sliding Window Maximum" (LeetCode 239) yêu cầu tìm giá trị lớn nhất trong mỗi cửa sổ trượt có kích thước cố định k khi di chuyển từ trái sang phải trên một mảng số nguyên.

Ví dụ

Đầu vào: nums = [1,3,-1,-3,5,3,6,7], k = 3
Đầu ra: [3,3,5,5,6,7]

Phân tích thuật toán

Cả hai cách tiếp cận đều sử dụng hàng đợi hai đầu (Deque) để duy trì một danh sách các chỉ mục (hoặc giá trị) theo thứ tự giảm dần. Phần tử đầu tiên của Deque luôn là giá trị lớn nhất trong cửa sổ hiện tại. Khi cửa sổ trượt:

• Thêm phần tử mới: Loại bỏ các phần tử nhỏ hơn ở cuối Deque, sau đó thêm phần tử mới vào cuối.
• Loại bỏ phần tử cũ: Nếu phần tử ở đầu Deque trùng với phần tử bị trượt ra, loại bỏ nó.

Cách 1: Đóng gói logic vào lớp MyQueue

import java.util.Deque;
import java.util.LinkedList;

class MonotonicQueue {
    private Deque<Integer> data = new LinkedList<>();

    // Thêm phần tử, duy trì thứ tự giảm dần
    public void push(int value) {
        while (!data.isEmpty() && value > data.peekLast()) {
            data.pollLast();
        }
        data.offerLast(value);
    }

    // Loại bỏ phần tử nếu nó đang ở đầu hàng đợi
    public void pop(int value) {
        if (!data.isEmpty() && data.peekFirst() == value) {
            data.pollFirst();
        }
    }

    // Lấy phần tử lớn nhất hiện tại
    public int getMax() {
        return data.peekFirst();
    }
}

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0) return new int[0];
        int n = nums.length;
        int[] result = new int[n - k + 1];
        MonotonicQueue queue = new MonotonicQueue();

        // Khởi tạo cửa sổ đầu tiên
        for (int i = 0; i < k; i++) {
            queue.push(nums[i]);
        }
        result[0] = queue.getMax();

        // Trượt cửa sổ
        for (int i = k; i < n; i++) {
            queue.pop(nums[i - k]);
            queue.push(nums[i]);
            result[i - k + 1] = queue.getMax();
        }
        return result;
    }
}

Cách 2: Xử lý trực tiếp không qua lớp phụ

import java.util.Deque;
import java.util.LinkedList;

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0) return new int[0];
        int n = nums.length;
        int[] result = new int[n - k + 1];
        Deque<Integer> deque = new LinkedList<>();

        // Xử lý các phần tử trong cửa sổ đầu tiên
        for (int i = 0; i < k; i++) {
            while (!deque.isEmpty() && nums[i] > deque.peekLast()) {
                deque.pollLast();
            }
            deque.offerLast(nums[i]);
        }
        result[0] = deque.peekFirst();

        // Duyệt qua các cửa sổ còn lại
        for (int i = k; i < n; i++) {
            // Loại bỏ phần tử vừa ra khỏi cửa sổ
            if (!deque.isEmpty() && deque.peekFirst() == nums[i - k]) {
                deque.pollFirst();
            }
            // Thêm phần tử mới vào cửa sổ
            while (!deque.isEmpty() && nums[i] > deque.peekLast()) {
                deque.pollLast();
            }
            deque.offerLast(nums[i]);
            result[i - k + 1] = deque.peekFirst();
        }
        return result;
    }
}

Độ phức tạp

• Thời gian: O(n), mỗi phần tử được thêm vào và xóa khỏi Deque tối đa một lần.
• Không gian: O(k), Deque lưu tối đa k phần tử.