单调队列

• OI Wiki: https://oi-wiki.org/ds/monotonous-queue/

题目	难度
239. 滑动窗口最大值	困难
1438. 绝对差不超过限制的最长连续子数组	困难	滑动窗口内最大最小值
2398. 预算内的最多机器人数目	困难	滑动窗口内最大值

java.util.Deque 类

Deque：

	First Element (Head)		Last Element (Tail)
	Throws exception	Special value	Throws exception	Special value
Insert	addFirst(e)	offerFirst(e)	addLast(e)	offerLast(e)
Remove	removeFirst()	pollFirst()	removeLast()	pollLast()
Examine	getFirst()	peekFirst()	getLast()	peekLast()

Queue：

	Queue Method	Equivalent Deque Method
	add(e)	addLast(e)
推荐	offer(e)	offerLast(e)
	remove()	removeFirst()
推荐	poll()	pollFirst()
	element()	getFirst()
推荐	peek()	peekFirst()

Stack：

	Stack Method	Equivalent Deque Method
入栈	push(e)	addFirst(e)
出栈	pop()	removeFirst()
栈顶元素	peek()	getFirst()

239. 滑动窗口最大值

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

public class Solution239 {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length;

        // 前 k 个
        Deque<Integer> deque = new ArrayDeque<>();
        for (int i = 0; i < k; i++) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.getLast()]) {
                deque.removeLast();
            }
            deque.addLast(i);
        }

        int[] res = new int[len - k + 1];
        res[0] = nums[deque.getFirst()];

        // k+1 到 len
        for (int i = k; i < len; i++) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.getLast()]) {
                deque.removeLast();
            }
            deque.addLast(i);

            while (deque.getFirst() <= i - k) {
                deque.removeFirst();
            }
            res[i - k + 1] = nums[deque.getFirst()];
        }
        return res;
    }
}

1438. 绝对差不超过限制的最长连续子数组

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

public class Solution1438 {
    public int longestSubarray(int[] nums, int limit) {
        int len = nums.length;

        Deque<Integer> deque1 = new ArrayDeque<>();
        Deque<Integer> deque2 = new ArrayDeque<>();

        int max = 0;
        // 双指针
        int left = 0;
        int right = 0;
        while (right < len) {
            // 滑动窗口最大值
            while (!deque1.isEmpty() && nums[right] > deque1.getLast()) {
                deque1.removeLast();
            }
            deque1.addLast(nums[right]);
            // 滑动窗口最小值
            while (!deque2.isEmpty() && nums[right] < deque2.getLast()) {
                deque2.removeLast();
            }
            deque2.addLast(nums[right]);

            // 左指针右移
            while (!deque1.isEmpty() && !deque2.isEmpty()
                    && deque1.getFirst() - deque2.getFirst() > limit) {
                if (nums[left] == deque1.getFirst()) {
                    deque1.removeFirst();
                }
                if (nums[left] == deque2.getFirst()) {
                    deque2.removeFirst();
                }
                left++;
            }

            max = Math.max(max, right - left + 1);
            right++;
        }
        return max;
    }
}

2398. 预算内的最多机器人数目

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

public class Solution2398 {
    public int maximumRobots(int[] chargeTimes, int[] runningCosts, long budget) {
        int n = chargeTimes.length;

        int left = 1;
        int right = n + 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            // 边界二分 F, F,..., F, [T, T,..., T]
            // ----------------------^
            if (!checkMid(chargeTimes, runningCosts, budget, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left - 1;
    }

    // true: 可以连续运行 k 个机器人
    private boolean checkMid(int[] chargeTimes, int[] runningCosts, long budget, int k) {
        int n = chargeTimes.length;

        // 滑动窗口最大值
        Deque<Integer> deque = new ArrayDeque<>();
        long max = 0;
        long sum = 0;

        // 前 k 个
        for (int i = 0; i < k; i++) {
            while (!deque.isEmpty() && chargeTimes[i] >= chargeTimes[deque.getLast()]) {
                deque.removeLast();
            }
            deque.addLast(i);
            sum += runningCosts[i];
        }

        max = chargeTimes[deque.getFirst()];
        if (max + k * sum <= budget) {
            return true;
        }

        // k+1 到 len
        for (int i = k; i < n; i++) {
            while (!deque.isEmpty() && chargeTimes[i] >= chargeTimes[deque.getLast()]) {
                deque.removeLast();
            }
            deque.addLast(i);
            while (deque.getFirst() <= i - k) {
                deque.removeFirst();
            }

            max = chargeTimes[deque.getFirst()];
            sum = sum + runningCosts[i] - runningCosts[i - k];

            long totalCost = max + k * sum;
            if (totalCost <= budget) {
                return true;
            }
        }
        return false;
    }
}

（全文完）