从头再来！社招找工作——算法题复习十一：单调栈/单调队列

从本篇博客开始，我们要开始介绍算法题中最难的几类。本篇博客首先介绍单调栈和单调队列。

单调栈

我们介绍一下单调栈的基本代码架构：定义一个栈stack，其中的数据类型是int型，保存的是数组的下标（而不是元素）！顾名思义，单调栈本身是一个栈，而且栈中的元素是有序的。但是，这里的单调和有序，并不是栈中元素单调和有序，因为栈中存储的是数组下标。不过数组下标对应的数组元素，确实是单调且有序的。这个差别一定要注意！
我们可以根据题目需求规定这个栈是递增或是递减的或是严格递增的或是严格递减的。我们来看一个例子，假设栈是递增的，即先入栈的元素小于后入栈的元素。对于一个数组 nums = [2, 4, 5, 3, 1]，遍历每个元素，stack会发生如下变化：

1. 首先将 nums[0] = 3 的下标 0 压入栈中，stack = [0]；
2. 设置索引 i 从 1 开始遍历到 len-1。当 i = 1 时，由于 nums[1] > nums[0]，符合递增的条件，因此将nums[1] 的下标 1 压入栈中，stack = [0,1]；
3. 当 i = 2 时，由于 nums[2] > nums[1]，符合递增的条件，将 2 压入栈中，stack=[0,1,2]；
4. 当 i = 3 时，发现 nums[3] < nums[2]，此时需要将栈顶元素 2 弹出栈，stack=[0,1]；接下来栈顶元素是 1，比较一下发现 nums[3] < nums[1]，同样地弹出 1，stack=[0]；终于我们找到nums[3] > nums[0]，0 不需要被弹出，此时将 3 压入栈中，stack=[0,3]；
5. 当 i = 4 时，发现 nums[4] < nums[3]，3 被弹出栈；依然有 nums[4] < nums[0]，0 也被弹出栈；此时栈已经空了，将 4 压入栈中，stack = [4]；

这就是遍历完整个数组，单调栈将发生的事情。将上述所有过程合并起来，可以得到一段简短的代码：

// 遍历 nums 数组的每个元素，在此过程中模拟单调栈 stack 中元素的情况
nums = {2, 4, 5, 3, 1};
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0;i < nums.length;i++) {
	while (!stack.isEmpty() && nums[i] < nums[stack.peek()]) {
		stack.poll();
	}
	stack.push(i);
}

基于有序和栈先进后出的特性，它能解决一类特定的算法题：寻找数组中某个下标后出现的某种和单调性相关的值。值得一提的是，单调栈运用到的是贪心思想，这个大家会在例题中有所感受。另外，单调栈每个元素最多只会入栈、出栈1次，所以单调栈的时间复杂度为O(n)。

每日以后的最高温度出现在第几天后（Easy）

Leetcode
给定一个整数数组 temperatures，表示每天的温度。返回一个数组 answer，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，则用 0 来代替。

这道题就是标标准准地用单调栈来解决的问题，甚至题干里都将“下一个单调递增的值的下标”这个要素都明白写出了。既然已知这道题要用单调栈来做了，那么接下来分析一下这个单调是递增还是递减呢。我们看到题目要求的是下一个更大的气温，所以我们应该设置一个递减的单调栈。这是不是有点不符合常理啊？不是哦，因为只有我们设置一个单调栈，当我们遇到下一个更大的气温时，才能知道这个高气温是前面多少个低气温的“下一个更大的气温”，且通过数组下标去计算相隔了多久。大家理清了这个设置递减的单调栈的思路，代码就很好写出来了：

public int[] dailyTemperatures(int[] temperatures) {
	Deque<Integer> stack = new ArrayDeque<>();
	int len = temperatures.length;
	int[] result = new int[len];
	for (int i = 0;i < len;i++) {
		while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) { // 递减的单调栈
			int lowTemp = stack.poll(); // 弹出低气温的下标
			result[lowTemp] = i - lowTemp; // 计算相隔几天
		}
		stack.push(i);
	}
	while (!stack.isEmpty()) { // 遍历结束后，单调栈中残留的元素代表它们没有下一个更大的气温了。但其实不需要，因为 result 中元素的默认值就是 0
		result[stack.poll()] = 0;
	}
	return result;
}

柱状图中最大矩形（Hard）

Leetcode
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1。求在该柱状图中，能够勾勒出来的矩形的最大面积。例图如下：

对于这道题，如果用暴力解法的话倒是也行。定义所要求的矩阵的底部长度为宽，高度为高，那么我们用一个二维循环去遍历宽 = 1 的 len 种情况、宽 = 2 的 len-1 种情况、……、宽 = len 的 1 种情况，分别求出对应的高，即宽覆盖的数组元素的最小值，相乘求得面积之后取最大值。这种暴力思想显然复杂度达到了O(n²)，得不到面试官的认可。

我们转换一下思维，刚才的暴力法里，我们先确定了宽，然后一直在求固定宽下的高。我们不妨先固定高，再来求当某个矩阵的高已知情况下，宽能是多少。
如果我们选中一根柱子，它的高是 heights[i]，那么要使一个包含该柱子的矩阵的高度为 heights[i]，这个矩阵的最左端柱子应该是“该柱子向左遍历第一个比它低的柱子的右边柱子”，最右端柱子应该是“该柱子向右遍历第一个比它低的柱子的左边柱子”。在这个柱子区间内，i 是最低或者最低之一的那根柱子，所形成的矩阵高度为 height[i]。
刚才在寻找“第一个比 i 低的柱子”过程，完全可以用单调栈来实现，只不过我们需要两个单调栈来分别做向左和向右的遍历。
在我们遍历柱子的高度时，有时间复杂度O(n)。单调栈每个元素最多只会入栈、出栈1次，所以单调栈的时间复杂度也为O(n)。好在，向左遍历的单调栈的实现过程可以和它同步，向右遍历的单调栈的实现过程也不依赖于它，两个时间复杂度应该加起来而不是乘起来，所以总体时间复杂度为O(n)，比暴力法好很多。

实现代码如下：

public int largestRectangleArea(int[] heights) {
	Deque<Integer> stack = new ArrayDeque<>();
	int len = heights.length;
	int[] left = new int[len]; // 矩阵左端
	for (int i = 0;i < len;i++) {
		while (!stack.isEmpty() && heights[i] <= heights[stack.peek()]) { // 严格递增的单调栈，用来找到第一个小于当前下标元素的元素的下标
			stack.poll();
		}
		if (stack.isEmpty()) {
			left[i] = 0; // 矩阵左端只能是最左端柱子
		}
		else {
			left[i] = stack.peek() + 1;
		}
		stack.push(i);
	}

	stack.clear();
	int[] right = new int[len]; // 矩阵右端
	for (int i = len - 1;i >= 0;i--) {
		while (!stack.isEmpty() && heights[i] <= heights[stack.peek()]) { // 严格递增的单调栈，用来找到第一个小于当前下标元素的元素的下标
			stack.poll();
		}
		if (stack.isEmpty()) {
			right[i] = len - 1; // 矩阵右端只能是最右端柱子
		}
		else {
			right[i] = stack.peek() - 1;
		}
		stack.push(i);
	}

	int max = 0;
	for (int i = 0;i < len;i++) {
		max = Math.max(heights[i]*(right[i]-left[i]+1), max);
	}
	return max;
}

接雨水（Hard）

Leetcode
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。例图如下：

这是一道相当经典的算法题了，甚至在脉脉上已经是一个“梗”了，表示面试官出这道就是在刁难我们或者劝退我们。事实上，这道题有三种解法，刚好对应前两篇博客和本篇博客的内容，分别是动态规划、双指针和单调栈。相信只要你用任意一个方法解出来，面试官都会对你刮目相看，我们一个一个来研究吧。

1. 动态规划
   首先，有了上一题的基启发，我们可以研究一下第 i 个柱子能接多少雨水。稍加思索我们可以得知，能接的雨水数量，应该是 min{柱子 i 左边的所有柱子的最高高度，柱子 i 右边的所有柱子的最高高度} - 柱子 i 的本身高度。得到这个式子后，我们计算出每根柱子的接水量，求出一个总和即可。
   那么接下来问题转化为如何求“柱子 i 左边的所有柱子的最高高度”和“柱子 i 右边的所有柱子的最高高度”。熟练掌握了动态规划方法的朋友们应该能快速写出代码了：

public int trap(int[] height) {
	int len = height.length;
	int[] left = new int[len]; // left[i] 表示，在 i 及其左边所有柱子中，最高的高度是多少
	left[0] = height[0];
	for (int i = 1;i < len;i++) {
		left[i] = Math.max(left[i-1], height[i]);
	}

	int[] right = new int[len]; // left[i] 表示，在 i 及其右边所有柱子中，最高的高度是多少
	right[len-1] = height[len-1];
	int sum = Math.min(left[len-1], right[len-1]) - height[len-1]; // 同时计算接水总量。其实 len-1 处接水量一定是0
	for (int i = len-2;i >= 0;i--) {
		right[i] = Math.max(right[i+1], height[i]);
		sum += Math.min(left[i], right[i]) - height[i];
	}
	
	return sum;
}

时间复杂度 O(n)，额外空间复杂度 O(n)。

2. 双指针
   我们想一下是否能缩减动态规划算法的额外空间复杂度。上述算法中，无法同时计算 left 和 right 数组，所以即便缩减了一种一个数组的维度，另外一个数组仍然缩减不了，额外空间复杂度仍为 O(n)。
   但是可以换一种思路，用双指针去获取左边和右边最高的高度，可以不需要建一个数组。让我们来看双指针的方法：
   一开始设置左指针 left = 0，右指针 right = len-1。同时设置 leftMax 表示左指针（包含）左边最高的高度，rightMax 表示右指针（包含）右边最高的高度。我们这样来改进一下算法：
   在 left < right 的情况下：
   （1）使用 height[left] 和 height[right] 去不断更新 leftMax 和 rightMax；
   （2）比较 height[left] 和 height[right] 的大小。不失一般性，我们分析 height[left] < heigth[right] 的情况。我们先来考虑下一步哪个指针移动，显然是更矮的柱子 left 需要移动，因为目前来看它能接的雨水至少要比 right 更多（这里运用了贪心思想）。left 这里能接的雨水量 = min{leftMax, left 右边的所有柱子的最高高度} - height[left]。这里我们先给出结论 leftMax <= rightMax <= left 右边的所有柱子的最高高度 => left 这里能接的雨水量 = leftMax - height[left]。接下来再来证明这个连续不等式：式子的右半部分好理解，局部最大值小于等于整体最大值；而左半部分我们用反证法来证明，如果 left 的左边有一个很高的柱子甚至比 rightMax 高，那么按照我们先前提出的“更矮的柱子需要移动”的贪心方法，left 根本就到不了现在的位置，会被那个很高的 leftMax 停住，因此存在矛盾，得证。
   height[left] >= heigth[right] 的情况同理。

根据上述分析，我们写出代码：

public int trap(int[] height) {
	int left = 0;
	int right = height.length - 1;
	int leftMax = 0;
	int rightMax = 0;
	int sum = 0;
	while (left <= right) {
		leftMax = Math.max(height[left], leftMax);
		rightMax = Math.max(height[right], rightMax);
		if (height[left] < height[right]) {
			sum += leftMax - height[left++];
		}
		else {
			sum += rightMax - height[right--];
		}
	}
	return sum;
}

3. 单调栈
   让我们忘记上述两种做法，来想想用单调栈怎么做。怎么样的柱子结构才能接住雨水呢？
   首先得是有三个柱子，我们先来考虑这三根柱子是连续的情况。从左到右我们分别计为A、B、C。然后A、B、C必须满足 A > B 且 C > B（等于都不行）。在满足这样的情况下，我们可以计算得到由 A、B、C 三根连续柱子接住的雨水量为 Math{A, C}- B。
   如果 A、B、C三者不连续呢？我们发现其实也有类似的规律。只要A、B、C 三根柱子是 (A, C) 区间中最高的三根柱子，且满足 A > B 且 C > B，则在该区间内 B 的上方，一定能接 (Math{A, C}-B)*((C的下标-1)-(A的下标+1)+1) 的雨水量。
   基于 A>B 的这一发现，我们将设置一个严格单调递减单调栈，用来存储可能的 A 柱和 B 柱。每当遇到一个满足条件的 C 柱时，不断弹出 B 柱并获取栈顶的 A 柱。在计算完当前 A、B、C 柱能接到的雨水量后，我们还要将 A 看作 B，循环判断是否还存在满足条件的三根柱子。
   如此得到代码：

public int trap(int[] height) {
	Deque<Integer> stack = new ArrayDeque<>();
	int sum = 0;
	for (int i = 0;i < height.length;i++) {
		while (!stack.isEmpty() && height[i] >= height[stack.peek()]) { // 递减单调栈
			int indexB = stack.poll();
			if (!stack.isEmpty() && height[stack.peek()] > height[indexB]) {
				// 这里可能存在 C == B 的情况，不过没关系，sum 自增 0
				sum += (Math.min(height[stack.peek()], height[i]) - height[indexB]) * ((i-1)-(stack.peek()+1)+1);
			}
		}
		stack.push(i);
	}
	return sum;
}

单调队列

相较于单调栈，单调队列其实就是给单调栈开放了一个从栈底“开后门”弹出数据的能力。什么时候需要开这个后门？往往就是有个滑动窗口，或者我们要从栈底获取递减栈的极大值或递增栈的极小值。我们边看例题边来体验。

滑动窗口最大值（Middle）

牛客网
Leetcode
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位，返回每次滑动窗口中的最大值。

首先，我们应该能熟练地使用优先队列/堆的方法来熟练解决这道题了。使用这种方法我觉得面试官应该也会很认同你的能力了，我们先给出优先队列的代码：

public int[] maxSlidingWindow(int[] nums, int k) {
	PriorityQueue<int[]> pq = new PriorityQueue<>(new Compartor<int[]>() {
		@Override
		public int compare(int[] o1, int[] o2) {
			return o1[1] != o2[1] ? o2[1] - o1[1] : o2[0] - o1[0];
		}
	});
	int len = nums.length;
	int[] result = new int[len-k+1];
	for (int i = 0;i < k;i++) {
		pq.offer(new int[]{i, nums[i]});
	}
	result[0] = pq.peek()[1];
	for (int i = k;i < len;i++) {
		pq.offer(new int[]{i, nums[i]});
		while (pq.peek()[0] <= i - k) {
			pq.poll();
		}
		result[i-k+1] = pq.peek()[1];
	}
	return result;
}

使用优先队列的算法的时间复杂度为O(nlgn)。

接着，我们来看用单调队列怎么做呢？我们改一下这道题，去掉滑动窗口的限制，然后让我们用单调栈（允许获取栈底数据）来做，我们怎么处理？这也是比较简单的，我们设置一个递减的单调栈，并从栈底获取全局最大值即可。那么现在有了个滑动窗口的限制，我们可以不断获取栈底的那个下标值，将栈底的不在滑动窗口内的数据弹出，“开后门”般做到“滑动窗口”。
代码如下：

public int[] maxSlidingWindow(int[] nums, int k) {
	Deque<Integer> deque = new ArrayDeque<>();
	int len = nums.length;
	for (int i = 0;i < k;i++) {
		while (!deque.isEmpty() && nums[i] >= nums[deque.peek()]) { // 严格递减单调队列
			deque.poll();
		}
		deque.push(i);
	}
	
	int[] result = new int[len-k+1];
	result[0] = nums[deque.peekLast()]; // 因为我们从队列头加入元素，因此要从队列尾获取极大值
	for (int i = k;i < len;i++) {
		while (!deque.isEmpty() && nums[i] > nums[deque.peek()]) {
			deque.poll();
		}
		deque.push(i);
		while (deque.peekLast() <= i - k) { // 判断队列尾是否还在滑动窗口中
			deque.pollLast();
		}
		result[i-k+1] = nums[deque.peekLast()];
	}
	return result;
}

绝对差不超过限制的最长连续子数组（Hard）

Leetcode
给你一个整数数组 nums，和一个表示限制的整数 limit，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit。如果不存在满足条件的子数组，则返回 0。

这道题，我们更有必要用可以双向获取值的单调栈，来获取当前滑动窗口中的较大值序列和较小值序列（需要建立两个不同增减性的单调栈），以判断新的数据是否能加入滑动窗口中了。将上一篇博客中讲过的滑动窗口技巧和本篇的单调队列相结合，思路是比较清楚的，但是具体实现上仍有很多细节值得思考，我们直接来看代码吧：

public int longestSubarray(int[] nums, int limit) {
	Deque<Integer> increase = new ArrayDeque<>(); // 递增单调栈，保存较小值序列。如果遇到重复元素，保存较前出现的
	Deque<Integer> decrease = new ArrayDeque<>(); // 递减单调栈，保存较大值序列。如果遇到重复元素，保存较前出现的
	int max = 0;
	int left = 0;
	for (int right = 0;right < nums.length;right++) {
		while (!increase.isEmpty() && nums[right] < nums[increase.peek()]) {
			increase.poll();
		}
		while (!decrease.isEmpty() && nums[right] > nums[decrease.peek()]) {
			decrease.poll();
		}
		increase.push(right);
		decrease.push(right);

		// 维护好两个单调队列之后，看看当前滑动窗口的最大值与最小值之差是否大于 limit，若大于则左指针不断向右移动，直到两个单调队列在弹出栈底元素之后满足条件，这样就形成了当前的滑动窗口
		while (!increase.isEmpty() && !decrease.isEmpty() && nums[decrease.peekLast()]-nums[increase.peekLast()] > limit) {
			if (left == increase.peekLast()) {
				increase.pollLast();
			}
			if (left == decrease.peekLast()) {
				decrease.pollLast();
			}
			left++;
		}
		max = Math.max(right - left + 1, max);
	}
	return max;
}