单调栈、单调队列：刷题必备系列

个人认为，仅仅以刷题数量作为算法掌握程度的标准是不准确的，甚至是偏激的。衡量刷题效果的其实是两点，一是真正掌握的算法技巧数量，二是语言的熟练应用的实战能力(搞个输入输出搞半天，肯定是不行的)。掌握了一种解题技巧，其实对一系列的题都是手到擒来。本文介绍的单调栈、单调队列就是两种不可或缺的刷题技巧

单调栈

单调栈，概念其实很简单，一个栈，里面的元素的大小按照他们所在栈内的位置，满足一定的单调性(递增或者递减)。

单调栈有一个重要的性质：**可以找到左边第一个比当前元素大的元素或者左边第一个比当前元素小的元素。**文字苍白无力，下面两个举个例子

对于数组
$[5, 3, 1, 4, 2]$

[5,3,1,4,2]

• 递减栈，可以找到左边第一个比当前元素大的元素

  开始栈空、将5、3、1依次入栈，当入4的时候，发生冲突，栈顶元素小于当前元素，依次出栈，直到无冲突发生，才入栈。出栈时，出栈元素的左边第一个比其大的元素为出栈后的栈顶元素。即出栈1时，1的左边第一个比其大的元素一定是出栈后的栈顶元素3

  

• 递减栈，可以找到左边第一个比当前元素小的元素

  开始栈空，5入栈，3入栈，发生冲突，栈顶元素大于当前元素，依次出栈，直到无冲突发生，才入栈，出栈时，出栈元素的左边第一个比其小的元素为出栈后的栈顶元素。即4出栈时，4的左边比其小的元素为出站后的栈顶元素1。

  

强调两点

• 数组从左向右遍历或者从右向左遍历，单调栈均有相应的性质
• 所有元素仅仅会出栈一次和入栈一次，所以时间复杂度为O(n)

大显身手

熟悉了基本性质，下面就是我们大显身手的时候了。

每日温度

import java.util.Stack; class Solution { public int[] dailyTemperatures(int[] T) { //找右边第一个比其大的元素 //从右往左遍历，构造递减栈 if(T == null || T.length == 0) return new int[0]; int n = T.length;         Stack<Integer> stack = new Stack<>(); int []res = new int[n]; for(int i = n-1; i >= 0; i--) { while(!stack.empty() && T[i] >= T[stack.peek()]) { int popIndex = stack.pop(); if(stack.empty()) continue;                 res[popIndex] = stack.peek() - popIndex; }             stack.push(i); } while(!stack.empty()) { int popIndex = stack.pop(); if(stack.empty()) continue;             res[popIndex] = stack.peek() - popIndex; } return res; } } 

下一个更大元素

import java.util.*; class Solution { public int[] nextGreaterElement(int[] nums1, int[] nums2) { int m = nums1.length; int n = nums2.length; //从右向左遍历 //构建单调减栈 //多了一个hashMap         HashMap<Integer, Integer> map = new HashMap<>(); int res[] = new int[m]; for(int i = 0; i < m; i++) {map.put(nums1[i], i); res[i] = -1;}         Stack<Integer> stack = new Stack<>(); for(int i = n-1; i >= 0; i--) { while(!stack.empty() && nums2[i] >= stack.peek()) { int popValue = stack.pop(); if(stack.empty()) continue; if(map.containsKey(popValue)) res[map.get(popValue)] = stack.peek(); }             stack.push(nums2[i]); } while(!stack.empty()) { int popValue = stack.pop(); if(stack.empty()) continue; if(map.containsKey(popValue)) res[map.get(popValue)] = stack.peek(); } return res; } } 

下一个更大元素II

接雨水

单调队列

单调队列，和单调栈的概念相似，一个队列，里面的元素的大小按照他们所在队列内的位置，满足一定的单调性(递增或者递减)。

单调队列性质是：递增队列，队首元素一定是当前队列最小值，递减队列，队首元素一定是当前队列最大值

下面以递减队列举例，还是数组
$[5,3,1,4,2]$

[5,3,1,4,2]

5、3、1依次入队列，4入队列的时候发生冲突，当前元素大于队尾元素，循环出队列(从队尾删除)直到无冲突。

对于上面解释两点，一是从队尾出队列，这里所说的队列是双端队列,两边都可以出队，入队。

二是，这单调队列和单调栈有什么区别，核心区别在于，单调队列，可以获取队首元素，而栈无法直接获取栈底元素

牛刀小试

滑动窗口最大值

class Solution { //单调递减队列 class QueueImp{         LinkedList<Integer> queue = new LinkedList<>(); //添加指定值 public void add(int value) { while(queue.size() != 0 && queue.peekLast() < value) {queue.pollLast();}             queue.offer(value); } //删除指定值 public void delete(int value) { if(queue.size() != 0 && queue.peek()== value)                 queue.poll(); } //返回队列最大值 public int max() { return queue.peek(); } } public int[] maxSlidingWindow(int[] nums, int k) { if(k <= 0 || nums == null || nums.length == 0) return new int[0];         QueueImp queue = new QueueImp(); int []res = new int[nums.length-k+1]; int t = 0; //初始化 for(int i = 0; i < k; i++) queue.add(nums[i]);         res[t++] = queue.max(); for(int i = k; i < nums.length; i++) { //删除             queue.delete(nums[i-k]); //添加             queue.add(nums[i]);             res[t++] = queue.max(); } return res; } }