单调队列优化

单调队列优化算法（Monotonic Queue Optimization）是一种优化技巧，通常用于解决一些需要维护滑动窗口中最大（最小）值的问题。以下是一个单调队列优化的Java代码示例，用于解决滑动窗口中的最大值问题：

import java.util.ArrayDeque;
import java.util.Deque;

public class MonotonicQueueOptimization {

    public static int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n - k + 1];
        int resultIndex = 0;
        Deque<Integer> deque = new ArrayDeque<>();  // 存储元素的下标

        for (int i = 0; i < n; i++) {
            // 保持队列单调递减，从队尾弹出小于当前元素的下标
            while (!deque.isEmpty() && deque.peekLast() < i - k + 1) {
                deque.pollLast();
            }

            // 保持队列单调递减，从队尾弹出小于当前元素的下标
            while (!deque.isEmpty() && nums[deque.peekFirst()] < nums[i]) {
                deque.pollFirst();
            }

            deque.offerFirst(i);

            // 更新结果数组
            if (i >= k - 1) {
                result[resultIndex++] = nums[deque.peekLast()];
            }
        }

        return result;
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;

        int[] result = maxSlidingWindow(nums, k);

        System.out.print("Max sliding window: ");
        for (int num : result) {
            System.out.print(num + " ");
        }
    }
}

在这个示例中，maxSlidingWindow 方法使用单调队列优化解决了滑动窗口中的最大值问题。算法通过维护一个单调递减的队列来存储当前窗口内的元素下标，从而在常数时间内找到窗口内的最大值。

请注意，单调队列优化通常适用于需要在滑动窗口内求最大值（最小值）的问题，可以根据问题的具体需求进行相应的修改。