单调栈

什么是单调栈

从栈顶到栈底的元素是严格递增（or递减）

有什么用

例如，求前i-1项比第i项大（小）的元素下标最接近的一个，最后输出一个数组

怎么办到的

以求大于第i项的第一个元素为例，以栈底到栈顶递减，栈顶比第i项小，就出栈，直到栈顶比第i项大，入栈

例题

求数组1,2,3,1,2,3,1,2,3,2,1,3,2,1，前i项中，比a[i]大，但是下标最接近的一个

关键代码

import java.util.*;

public class SingleStack {

    public static void main(String[] args) {
        int[] arr = new int[]{1, 2, 3, 1, 2, 3, 1, 2, 3, 2, 1, 3, 2, 1};
        System.out.println(Arrays.toString(arr));
        Deque<Integer> deque = new ArrayDeque<>();
        for (int num : arr) {
            while (!deque.isEmpty() && deque.peek() <= num) {
                deque.pop();
            }
            if (deque.isEmpty()) {
                System.out.print("-1 ");
            } else {
                System.out.print(" " + deque.peek() + " ");
            }
            deque.push(num);
        }
        System.out.println();
    }
}

输出

[1, 2, 3, 1, 2, 3, 1, 2, 3, 2, 1, 3, 2, 1]
-1 -1 -1  3  3 -1  3  3 -1  3  2 -1  3  2 

单调队列

什么是单调队列

从队头到队尾的元素是严格递增（or递减）

有什么用

例如，求第i项到第i+k-1项的最大（小）元素，最后输出一个数组

怎么办到的

保证是双端队列，以求前k项最大值为例，以队首到队尾是递减，队列保存数组下标，当队首下标小于等于i-k时出队（保证队列中只存储i-k+1到i），当队尾元素大于第i项的时候入队，否则不但不入队，队尾还要出队，直到第i项能入队

例题

求数组1,2,3,4,1,2,3,4,1,2,3,4,3,2,1,4,3,2,1，每3个元素的最大值

关键代码

import java.util.*;

public class SingleQueue {

    public static void main(String[] args) {
        int[] arr = new int[]{1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, 3, 2, 1, 4, 3, 2, 1};
        int k = 3;
        System.out.println(Arrays.toString(arr));
        LinkedList<Integer> queue = new LinkedList<>();
        for (int i = 0; i < arr.length; i++) {
            int num = arr[i];
            while (!queue.isEmpty() && queue.getFirst() <= i - k) {
                queue.pollFirst();
            }
            while (!queue.isEmpty() && arr[queue.getLast()] <= num) {
                queue.pollLast();
            }
            queue.offerLast(i);
            System.out.print(" " + arr[queue.getFirst()] + " ");
        }
        System.out.println();
    }
}

输出

[1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, 3, 2, 1, 4, 3, 2, 1]
 1  2  3  4  4  4  3  4  4  4  3  4  4  4  3  4  4  4  3