單調佇列（雙端佇列）

// Java — LC 239 Sliding Window Maximum
// time = O(N), space = O(K)
public int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    int[] result = new int[n - k + 1];
    Deque<Integer> deque = new ArrayDeque<>(); // stores indices

    for (int i = 0; i < n; i++) {
        // Remove elements outside the window
        while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
            deque.pollFirst();
        }
        // Remove smaller elements from back (they'll never be the max)
        while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
            deque.pollLast();
        }
        deque.offerLast(i);
        // Window is fully formed
        if (i >= k - 1) {
            result[i - k + 1] = nums[deque.peekFirst()];
        }
    }
    return result;
}

# Python — LC 239 Sliding Window Maximum
# time = O(N), space = O(K)
from collections import deque

def maxSlidingWindow(nums, k):
    dq = deque()  # stores indices, front = max
    result = []
    for i, num in enumerate(nums):
        # Remove out-of-window
        while dq and dq[0] < i - k + 1:
            dq.popleft()
        # Remove smaller from back
        while dq and nums[dq[-1]] < num:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

// Java — LC 1696 Jump Game VI
// dp[i] = max(dp[j] for j in [i-k, i-1]) + nums[i]
// time = O(N), space = O(N)
public int maxResult(int[] nums, int k) {
    int n = nums.length;
    int[] dp = new int[n];
    dp[0] = nums[0];
    Deque<Integer> deque = new ArrayDeque<>();
    deque.offerLast(0);

    for (int i = 1; i < n; i++) {
        // Remove out-of-range
        while (!deque.isEmpty() && deque.peekFirst() < i - k) {
            deque.pollFirst();
        }
        dp[i] = dp[deque.peekFirst()] + nums[i];
        // Maintain decreasing order of dp values
        while (!deque.isEmpty() && dp[deque.peekLast()] <= dp[i]) {
            deque.pollLast();
        }
        deque.offerLast(i);
    }
    return dp[n - 1];
}

# Python — LC 1696 Jump Game VI
from collections import deque

def maxResult(nums, k):
    n = len(nums)
    dp = [0] * n
    dp[0] = nums[0]
    dq = deque([0])

    for i in range(1, n):
        while dq and dq[0] < i - k:
            dq.popleft()
        dp[i] = dp[dq[0]] + nums[i]
        while dq and dp[dq[-1]] <= dp[i]:
            dq.pop()
        dq.append(i)
    return dp[-1]

# Python — LC 862 (handles negative numbers via prefix sum + monotonic deque)
# time = O(N), space = O(N)
from collections import deque

def shortestSubarray(nums, k):
    n = len(nums)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]

    dq = deque()  # increasing deque of indices into prefix
    ans = n + 1

    for i in range(n + 1):
        # If prefix[i] - prefix[dq.front] >= k, we found a valid subarray
        while dq and prefix[i] - prefix[dq[0]] >= k:
            ans = min(ans, i - dq.popleft())
        # Maintain increasing order of prefix values
        while dq and prefix[dq[-1]] >= prefix[i]:
            dq.pop()
        dq.append(i)

    return ans if ans <= n else -1

// java
// LC 480 - Sliding Window Median
// IDEA: keep window split into two ordered halves: small (lower half) / large (upper half).
//       Invariant: small.size() == large.size()  OR  small.size() == large.size() + 1
//       => median is small.last() (odd k) or avg(small.last(), large.first()) (even k).
//       TreeSet stores INDICES with a (value, index) comparator, so duplicates are kept distinct.
// time = O(N log K), space = O(K)
public double[] medianSlidingWindow(int[] nums, int k) {
    Comparator<Integer> byVal = (a, b) ->
            nums[a] != nums[b] ? Integer.compare(nums[a], nums[b]) : Integer.compare(a, b);
    TreeSet<Integer> small = new TreeSet<>(byVal);  // lower half, max at last()
    TreeSet<Integer> large = new TreeSet<>(byVal);  // upper half, min at first()
    double[] res = new double[nums.length - k + 1];

    for (int i = 0; i < nums.length; i++) {
        // --- add index i, then rebalance ---
        small.add(i);
        large.add(small.pollLast());
        if (large.size() > small.size()) small.add(large.pollFirst());

        if (i >= k - 1) {
            res[i - k + 1] = (k % 2 == 1)
                    ? (double) nums[small.last()]
                    // cast BOTH: nums[i] can be Integer.MAX_VALUE -> int sum overflows
                    : ((double) nums[small.last()] + (double) nums[large.first()]) / 2.0;

            // --- remove the index leaving the window, then rebalance ---
            int out = i - k + 1;
            if (!small.remove(out)) large.remove(out);
            if (small.size() < large.size()) small.add(large.pollFirst());
            else if (small.size() > large.size() + 1) large.add(small.pollLast());
        }
    }
    return res;
}

# python
# LC 480 - Sliding Window Median
# IDEA: two heaps + LAZY DELETION. heapq has no remove(), so mark a value as
#       "delayed" and only physically pop it once it surfaces at a heap top.
#       Keep LOGICAL sizes separately (small_sz / large_sz) — len(heap) is unreliable.
# time = O(N log N), space = O(N)
import heapq
from collections import defaultdict

def medianSlidingWindow(nums, k):
    small, large = [], []        # small: max-heap (negated) = lower half; large: min-heap = upper half
    delayed = defaultdict(int)   # value -> pending deletions
    small_sz = large_sz = 0      # logical sizes

    def prune(heap):
        # drop already-deleted values sitting on top
        while heap:
            v = -heap[0] if heap is small else heap[0]
            if delayed[v] > 0:
                delayed[v] -= 1
                heapq.heappop(heap)
            else:
                break

    def rebalance():
        nonlocal small_sz, large_sz
        if small_sz > large_sz + 1:
            heapq.heappush(large, -heapq.heappop(small))
            small_sz -= 1; large_sz += 1
            prune(small)
        elif small_sz < large_sz:
            heapq.heappush(small, -heapq.heappop(large))
            large_sz -= 1; small_sz += 1
            prune(large)

    def add(v):
        nonlocal small_sz, large_sz
        if not small or v <= -small[0]:
            heapq.heappush(small, -v); small_sz += 1
        else:
            heapq.heappush(large, v); large_sz += 1
        rebalance()

    def remove(v):
        nonlocal small_sz, large_sz
        delayed[v] += 1
        if small and v <= -small[0]:
            small_sz -= 1
            if v == -small[0]:
                prune(small)
        else:
            large_sz -= 1
            if large and v == large[0]:
                prune(large)
        rebalance()

    res = []
    for i, v in enumerate(nums):
        add(v)
        if i >= k - 1:
            res.append(float(-small[0]) if k % 2 else (-small[0] + large[0]) / 2.0)
            remove(nums[i - k + 1])
    return res

# One-liner alternative if `sortedcontainers` is allowed (O(N log K)):
#   sl = SortedList(nums[:k]); median = (sl[k // 2] + sl[(k - 1) // 2]) / 2.0
#   then per step: sl.remove(nums[i - k]); sl.add(nums[i])

// java
// LC 995 - Minimum Number of K Consecutive Bit Flips
// IDEA: greedy left-to-right — if the EFFECTIVE value at i is 0, we must flip [i, i+k-1].
//       Queue keeps start indices of flips still covering i; pop front once front + k <= i.
//       effective(i) = nums[i] XOR (q.size() % 2)  ->  need flip when (q.size() + nums[i]) is even.
// time = O(N), space = O(K)
public int minKBitFlips(int[] nums, int k) {
    Deque<Integer> q = new ArrayDeque<>();  // start indices of active flips
    int res = 0;
    for (int i = 0; i < nums.length; i++) {
        if (!q.isEmpty() && q.peekFirst() + k <= i) q.pollFirst();  // flip expired
        if ((q.size() + nums[i]) % 2 == 0) {                        // effective bit is 0
            if (i + k > nums.length) return -1;                     // no room to flip
            q.offerLast(i);
            res++;
        }
    }
    return res;
}

# python
# LC 995 - Minimum Number of K Consecutive Bit Flips
# time = O(N), space = O(K)
from collections import deque

def minKBitFlips(nums, k):
    q = deque()   # start indices of flips still in effect
    res = 0
    for i, x in enumerate(nums):
        if q and q[0] + k <= i:
            q.popleft()
        if (len(q) + x) % 2 == 0:      # effective bit is 0 -> must flip here
            if i + k > len(nums):
                return -1
            q.append(i)
            res += 1
    return res

// java
// LC 918 - Maximum Sum Circular Subarray
// IDEA: duplicate the array (length 2n) so every wrap-around subarray becomes a normal one.
//       Answer = max over i of prefix[i] - min(prefix[j]) for j in [i-n, i-1].
//       Increasing deque of prefix indices: front = smallest prefix still in range.
//       Works for all-negative input (single elements are always candidates).
// time = O(N), space = O(N)
public int maxSubarraySumCircular(int[] nums) {
    int n = nums.length;
    int[] prefix = new int[2 * n + 1];
    for (int i = 0; i < 2 * n; i++) prefix[i + 1] = prefix[i] + nums[i % n];

    Deque<Integer> dq = new ArrayDeque<>();   // indices into prefix, increasing prefix values
    dq.offerLast(0);
    int ans = Integer.MIN_VALUE;

    for (int i = 1; i <= 2 * n; i++) {
        while (!dq.isEmpty() && dq.peekFirst() < i - n) dq.pollFirst();   // length cap
        ans = Math.max(ans, prefix[i] - prefix[dq.peekFirst()]);
        while (!dq.isEmpty() && prefix[dq.peekLast()] >= prefix[i]) dq.pollLast();
        dq.offerLast(i);
    }
    return ans;
}

# python
# LC 918 - Maximum Sum Circular Subarray
# time = O(N), space = O(N)
from collections import deque

def maxSubarraySumCircular(nums):
    n = len(nums)
    prefix = [0] * (2 * n + 1)
    for i in range(2 * n):
        prefix[i + 1] = prefix[i] + nums[i % n]

    dq = deque([0])          # increasing prefix values
    ans = float('-inf')
    for i in range(1, 2 * n + 1):
        while dq and dq[0] < i - n:      # subarray length must stay <= n
            dq.popleft()
        ans = max(ans, prefix[i] - prefix[dq[0]])
        while dq and prefix[dq[-1]] >= prefix[i]:
            dq.pop()
        dq.append(i)
    return ans

# Note: the O(1)-space "Kadane" solution is max(maxKadane, total - minKadane),
# with the guard: if maxKadane < 0 (all negatives) return maxKadane.

Need sliding window max/min?
  → Monotonic Deque: O(N) time, O(K) space
  → Alternative: Heap O(N log N) — slower but simpler

DP transition = max/min over a range of size K?
  → Monotonic Deque optimization: O(N) instead of O(N·K)

Subarray sum with negative numbers?
  → Prefix sum + monotonic deque (LC 862 pattern)

Need BOTH min and max in window?
  → Two deques: one increasing, one decreasing