单调栈、单调队列及其应用

单调栈定义

单调栈，顾名思义，即内部元素满足单调递增（递减）的栈，下面用Java代码展示一个栈内单调递减的实现：

public static void main(String[] args) {
    int[] nums = { 3, 7, 6, 5, 4, 1, 8, 2 };
    Deque<Integer> stack = new LinkedList<>();
    for (int num : nums) {
        // 如果栈非空，判断栈顶元素是否小于当前遍历到的 num
        // 如果栈顶元素小于 num, 说明 num 入栈后就无法满足单调递减
        // 循环遍历弹出所有小于 num 的元素，以便满足 num 入栈后，栈内元素依旧单调递减
        while (!stack.isEmpty() && stack.peekLast() < num) {
            stack.pollLast();
        }
        // 到这里，栈内要么为空, 要么都是大于 num 的元素
        // num 入栈，依旧满足单调递减
        stack.addLast(num);
        System.out.println(stack);
    }
}

// 运行结果如下：
[3]                - 栈空，3入栈
[7]                - 栈顶为3，小于7，不满足递减，3出栈，栈空循环结束，7入栈
[7, 6]             - 栈顶为7，大于6，6入栈
[7, 6, 5]          - 栈顶为6，大于5，5入栈
[7, 6, 5, 4]       - 栈顶为5，大于4，4入栈
[7, 6, 5, 4, 1]    - 栈顶为4，大于1，1入栈
[8]                - 栈内元素均小于8，挨个判断并出栈，直到栈空循环结束，然后8入栈
[8, 2]             - 栈顶为8，大于2，2入栈

单调栈应用

下面来展示具体应用：

下一个更大元素 Ⅰ

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/next-greater-element-i
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

由于题目说明数组中不存在重复元素，而且nums1是nums2的子集，所以我们可以先不管nums1，使用一个Map保存nums2中每一个元素的下一个更大的数字即可，下面展示具体实现：

public int[] nextGreaterElement(int[] nums1, int[] nums2) {
    // 根据 nums2 获取保存 nums2 中每一个元素的<下一个更大的数字>的 Map
    Map<Integer, Integer> map = getMap(nums2);
    for (int i = 0; i < nums1.length; i++) {
        // 如果 Map 中存在指定数字的 key, 说明该数字存在<下一个更大的数字>
        // 否则说明该数字仍然保存在栈中未弹出, 即不存在<下一个更大的数字>, 返回-1
        nums1[i] = map.getOrDefault(nums1[i], -1);
    }
    return nums1;
}

private Map<Integer, Integer> getMap(int[] nums) {
    Map<Integer, Integer> map = new HashMap<>();
    Deque<Integer> stack = new LinkedList<>();
    for (int num : nums) {
        // 如果栈非空，判断栈顶元素是否小于当前遍历的 num
        // 如果满足则说明栈顶元素的<下一个更大的数字>为 num
        // 弹出栈顶元素并保存在 Map 中, 开始下一个判断
        while (!stack.isEmpty() && stack.peekLast() < num) {
            map.put(stack.pollLast(), num);
        }
        // 到这里，栈内要么为空, 要么栈顶元素大于 num
        // 即栈顶元素的<下一个更大的数字>不是 num, num 入栈
        stack.addLast(num);
    }
    return map;
}

每日温度

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/daily-temperatures
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

由于此题要求我们存储的是和下一个更大数字之间的距离，因此我们只要在栈内储存元素的下标即可，下面是实现：

public int[] dailyTemperatures(int[] T) {
    int n = T.length;
    int[] res = new int[n];
    Deque<Integer> stack = new LinkedList<>();
    for (int i = 0; i < n; i++) {
        // 如果栈非空，判断栈顶元素下标对应的温度是否小于遍历的当前 T[i] 温度
        // 如果小于则说明当前温度 T[i] 比栈顶元素下标对应的温度高
        // 弹出元素，记录该下标与当前温度 T[i] 之间的距离，然后判断下一个元素
        while (!stack.isEmpty() && T[stack.peekLast()] < T[i]) {
            res[stack.peekLast()] = i - stack.pollLast();
        }
        stack.addLast(i);
    }
    return  res;
}

单调队列介绍及应用

单调队列中的其实并不是表面意义上的普通队列，而指的是双向队列，具体实现是当在添加元素时和单调栈一样都是在尾部进行操作，但是在取元素时则是从头部就行获取，下面就以一道经典的滑动窗口题展示其具体应用：

滑动窗口最大值

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sliding-window-maximum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

我们只需要维护一个单调递减的队列，这样队头就一直是最大值，队列内保存元素的下标，并且当队头元素存储的下标不在符合的范围内时，需要从队头出头：

public int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    int pos = 0;
    int resArrLen = n - k + 1;
    int[] res = new int[resArrLen];
    Deque<Integer> deque = new LinkedList<>();
    for (int i = 0; i < n; i++) {
        // 添加元素和单调栈是一个思路
        while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
            deque.pollLast();
        }
        deque.addLast(i);
        // 判断当前下标是否大于等于区间范围
        // 满足了才开始添加值
        if (i >= k - 1) {
            // 获取队头存储的下标
            Integer tmp = deque.peekFirst();
            // 判断队头的下标是否在区间范围内
            // 如果大于就从队头出队
            if (i - tmp > k - 1) {
                deque.pollFirst();
            }
            // 然后当前队头即为区间范围内的最大值
            res[pos++] = nums[deque.peekFirst()];
        }
    }
    return res;
}