【数据结构与算法】单调队列

🌠作者：@阿亮joy.
🎆专栏：《数据结构与算法要啸着学》
🎇座右铭：每个优秀的人都有一段沉默的时光，那段时光是付出了很多努力却得不到结果的日子，我们把它叫做扎根

👉滑动窗口的最大值👈

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

返回滑动窗口中的最大值。

这是一道可以使用单调队列的经典题。如果使用暴力方法的话，就是遍历一遍的过程中每次从窗口中再找到最大的数值，这样很明显是 O(k × N) 的算法。而使用单调队列来解这道题目，时间复杂度是 O(N)。

那什么是单调队列呢？单调队列是具有单调性的队列，其里面存储的元素单增或者单减。单调队列需要保证的一个功能就是：每次插入元素或者删除元素，其队头的元素都是最大值或者最小值。为了实现这个功能，我们需要用双端队列 deque 来做适配器。

为了说明单调队列的功能，假设数组中的元素是 6 4 2 5 3。注：一下过程假设队头数据是最大值，队头数据是最小值同理。窗口的右边界往右移动，则说明要插入新数据。如果新插入的数据比队尾的数据小，则直接将数据从队尾插入；而如果新插入的数据对队尾的数据大，则需要将队尾数据弹出直至队尾数据大于新插入的数据或队列为空。窗口的左边界往右移动，则说明可能要弹出队头数据。如果从窗口出来的数据就是队头数据，则说明队头数据已过期，需要将队头数据弹出；而如果从窗口出来的数据不是队头数据，则不需要弹出队头数据。

在这里插入图片描述

为什么单调队列就能够保证它里面存储的就是窗口内的最大值呢？其实它是通过新加入的值是否会比前面的值大，如果是，就将前面的元素从尾部弹出。因为新加入的元素肯定比它们晚离开窗口，而且值有比它们大，所以只需要保留新加入元素就可以保证窗口内的最大值在队列中。

那如何估计单调队列解决滑动窗口最大值的时间复杂度呢？数组中的每个元素最多进队列一次，出队列一次，没有多余的操作，所以整体的时间复杂度为 O(N)，每次操作的平均复杂度为 O(1)。

👉单调队列的实现👈

// MyQueue.h
#pragma once
#include <deque>
#include <iostream>
#include <vector>
#include <assert.h>
using namespace std;class MyQueue
{
public:// 因为范围是左必右开的,所以_left初始为-1,_right初始为0// [_left, _right)MyQueue(const vector<int>& arr): _arr(arr), _left(-1), _right(0){}void push(){// 数组中的元素都进入过单调队列中了if (_right == _arr.size())return;// 加入新元素时,将队尾元素弹出至队列为空或队尾元素大于新加入的元素while (!_q.empty() && _arr[_q.back()] <= _arr[_right]){_q.pop_back();}_q.push_back(_right);++_right;}// _arr [_left, _right)void pop(){// 左边界大于等于右边界,说明窗口内没有数据了,// 直接返回即可if (_left >= _right - 1)return;// 因为_left初始值是-1,所以需要先加加_left++_left;if (_q.front() == _left){_q.pop_front();}}int front(){// 如果队列为空,直接断言报错assert(!_q.empty());	return _arr[_q.front()];}private:int _left;	// 窗口的左边界int _right;	// 窗口的右边界的再右一个位置deque<int> _q;	// 使用双端队列来实现单调队列,双端队列中存的是下标vector<int> _arr;
};

MyQueue 类使用说明：

申请一个滑动窗口对象时，需要传入一个 vector 对象。
上面的滑动窗口类可以自己手动控制滑动窗口的大小。使用一次 push 接口，就表明滑动窗口的右边界向右移动；而使用一次 pop 接口，就表明滑动窗口的左边界向右移动。滑动窗口左右边界向右移动，双端队列中存储的数据会是否需要弹出，见上文讲解！

知道如何使用 MyQueue 类后，我们就可以轻松地解决最开始的题目了。

注：需要将 MyQueue 类拷贝到 LeetCode 上

class Solution 
{
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {MyQueue q(nums);// 形成大小为k的窗口for(int i = 0; i < k; ++i){q.push();}vector<int> ret;ret.push_back(q.front());   // 将当前窗口中的最大值尾插到ret中for(int i = k; i < nums.size(); ++i){// 左右边界同时向右移动一次即可保存滑动窗口的大小为kq.push();q.pop();ret.push_back(q.front());   // 记录滑动窗口的最大值}return ret;}
};

在这里插入图片描述

注：单调队列的实现方式有很多，需要根据具体的题目来定制相应的单调队列，不能死板地认为单调队列只有一种实现方式。

👉单调栈的实现👈

单调栈也是具有单调性的栈，其存储的元素是单增或者单剪。单调栈通常用于寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置。

给定数组 arr = { 5 4 3 6 1 2 0 7 }，请你求出数组中每个元素的左边和右边第一个比自己大的元素。暴力的方法，来到 i 位置，向左向右遍历找出第一个比 i 位置上元素大的元素。很明显，这种方式的时间复杂度为 O(N^2)。

如果采用单调栈呢，解决上面问题的时间复杂度为 O(N)。过程如下图：

在这里插入图片描述
为什么上面的过程就能够求出每个元素左边和右边第一个比自己大的元素呢？证明如下图：

在这里插入图片描述

如果数组中有重复的元素，那么栈中里面放的就不再是下标了，而是存储下标的 list 或者 vector。当新加入的元素比栈顶元素大时，那么就生成信息了。那如何生成呢？新加入的元素就是第一个比栈顶元素大的元素，栈顶元素下面压着的链表尾部的元素就是左边第一个比栈顶元素大的元素。如果新加入的元素和栈顶元素相等，那么新加入元素的下标尾插到 list 或 vector 中。

单调栈的实现，在这里我就不实现成一个类了，而将其实现出一个函数。如果大家想将其实现成一个类，可以参考下面的代码来实现。

数组无重复值版本的单调栈

vector<vector<int>> getNearBiggerNoRepeat1(const vector<int> arr)
{// ret[i][0]存的值是左边第一个比arr[i]大的值的下标// ret[i][1]存的值是右边第一个比arr[i]大的值的下标vector<vector<int>> ret(arr.size(), vector<int>(2));stack<int> st;for (int i = 0; i < arr.size(); ++i){// arr[i]为新插入的元素while (!st.empty() && arr[st.top()] < arr[i]){int popIndex = st.top();st.pop();// 如果左边没有比自己大的数,左边界的下标设置为-1int leftBiggerIndex = st.empty() ? -1 : st.top();ret[popIndex][0] = leftBiggerIndex;// 如果新插入元素比栈顶元素大,那么新插入元素就是// 右边第一个比栈顶元素大的元素ret[popIndex][1] = i;}// 添加元素操作不要忘了st.push(i);}// 生成栈中元素的信息while (!st.empty()){int popIndex = st.top();st.pop();// 如果左边没有比自己大的数,左边界的下标设置为-1int leftBiggerIndex = st.empty() ? -1 : st.top();ret[popIndex][0] = leftBiggerIndex;// 如果新插入元素比栈顶元素大,那么新插入元素就是// 右边第一个比栈顶元素大的元素ret[popIndex][1] = -1;}return ret;
}

现在数组无重复值版本的单调栈就实现好了，我们找到题目来验证一下写得对不对吧！

每日温度

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

很明显，每日温度这道题目就可以通过单调栈来解决。而且这道题目只要求求出右边第一个比自己大的值就行了，并不需要求左边第一个比自己大的值。那么就把上面的实现的单调栈代码拷贝到 LeetCode 去，再实现下面的代码就行了。

vector<vector<int>> getNearBiggerNoRepeat(const vector<int>& arr)
{// ret[i][0]存的值是左边第一个比arr[i]大的值的下标// ret[i][1]存的值是右边第一个比arr[i]大的值的下标vector<vector<int>> ret(arr.size(), vector<int>(2));stack<int> st;for (int i = 0; i < arr.size(); ++i){// arr[i]为新插入的元素while (!st.empty() && arr[st.top()] < arr[i]){int popIndex = st.top();st.pop();// 如果左边没有比自己大的数,左边界的下标设置为-1int leftBiggerIndex = st.empty() ? -1 : st.top();ret[popIndex][0] = leftBiggerIndex;ret[popIndex][1] = i;}// 添加元素操作不要忘了st.push(i);}// 生成栈中元素的信息while (!st.empty()){int popIndex = st.top();st.pop();int leftBiggerIndex = st.empty() ? -1 : st.top();ret[popIndex][0] = leftBiggerIndex;ret[popIndex][1] = -1;}return ret;
}class Solution 
{
public:vector<int> dailyTemperatures(vector<int>& temperatures) {vector<vector<int>> info = getNearBiggerNoRepeat(temperatures);vector<int> ret(temperatures.size());for(size_t i = 0; i < temperatures.size(); ++i){// info[i][1] 等于 -1 表示 temperature[i] 右边没有比它更高的温度了// info[i][0] 不等于 -1 表示 temperature[i] 右边有比它更高的温度// 最近的一天是在 info[i][1] - i 天后if(info[i][1] != -1)ret[i] = info[i][1] - i;elseret[i] = 0;}return ret;}
};

在这里插入图片描述

用我们上面实现的单调栈来解决这道题目，简直就是杀鸡用牛刀。解决这道题目，我们只需要实现单调栈的主要逻辑就行了，如下方代码所示：

class Solution 
{
public:vector<int> dailyTemperatures(vector<int>& temperatures) {vector<int> ret(temperatures.size());stack<int> st;st.push(0); // 数组第一个元素先入栈for(int i = 1; i < temperatures.size(); ++i){// 栈顶元素比新加入元素temperatures[i]小// 就要生成栈顶元素的信息while(!st.empty() && temperatures[st.top()] < temperatures[i]){int popIndex = st.top();st.pop();ret[popIndex] = i - popIndex;}st.push(i);}// 循环结束,栈中的元素也要生成信息while(!st.empty()){int popIndex = st.top();st.pop();ret[popIndex] = 0;}return ret;}
};

在这里插入图片描述

数组有重复值版本的单调栈

vector<vector<int>> getNearBiggerRepeat(const vector<int>& arr)
{// ret[i][0]存的值是左边第一个比arr[i]大的值的下标// ret[i][1]存的值是右边第一个比arr[i]大的值的下标vector<vector<int>> ret(arr.size(), vector<int>(2));stack<vector<int>> st;for (int i = 0; i < arr.size(); ++i){while (!st.empty() && arr[st.top()[0]] < arr[i]){vector<int> popVector = st.top();st.pop();int leftBiggerIndex = st.empty() ? -1 : st.top()[st.top().size() - 1];for (int popIndex : popVector){ret[popIndex][0] = leftBiggerIndex;ret[popIndex][1] = i;}}// 添加操作if (!st.empty() && arr[st.top()[0]] == arr[i]){st.top().push_back(i);}else{vector<int> v;v.push_back(i);st.push(v);}}while (!st.empty()){vector<int> popVector = st.top();st.pop();int leftBiggerIndex = st.empty() ? -1 : st.top()[st.top().size() - 1];for (int popIndex : popVector){ret[popIndex][0] = leftBiggerIndex;ret[popIndex][1] = -1;}}return ret;
}void Test()
{vector<int> arr = { 2, 3, 2, 5,6,7,3,3,3,5,8 };vector<vector<int>> ret = getNearBiggerRepeat(arr);for (int i = 0; i < ret.size(); ++i){cout << ret[i][0] << " : " << ret[i][1] << endl;}
}

在这里插入图片描述

指标A的最大值

数组中所有数都是正数，数组中累加和与最小值的乘积，假设叫做指标 A。给定一个数组，请返回子数组中，指标 A 最大的值。

思路：求出数组中每个元素作为最小值时的指标 A，要使子数组的指标 A 最大，那么就要使子数组的累加和最大。那怎么才能让子数组的累加和最大呢？就是找到左边和右边第一个比自己小的元素，这样就能让子数组的累加和最大了。很明显，这就需要用到单调栈了。

class Solution
{
public:int max(vector<int>& arr){int max = -1;stack<int> st;st.push(0);for (int i = 1; i < arr.size(); ++i){// 该单调栈栈底元素是最大的,栈底元素是最小的while (!st.empty() && arr[st.top()] >= arr[i]){int popIndex = st.top();st.pop();// 栈为空时,说明从0到i-1的数中arr[popIndex]是最小的// 栈不为空时,说明从st.top()+1到i-1的数中arr[popIndex]是最小的int leftSmallerIndex = !st.empty() ? st.top() + 1 : 0;int sum = 0;for (int j = leftSmallerIndex; j < i; ++j){sum += arr[j];}max = sum * arr[popIndex] > max ? sum * arr[popIndex] : max;}st.push(i);}// 循环结束,栈中的元素右边全是比自己大的数while (!st.empty()){int popIndex = st.top();st.pop();// 栈为空时,说明从0到i-1的数中arr[popIndex]是最小的// 栈不为空时,说明从st.top()+1到i-1的数中arr[popIndex]是最小的int leftSmallerIndex = !st.empty() ? st.top() + 1 : 0;int sum = 0;for (int j = leftSmallerIndex; j < arr.size(); ++j){sum += arr[j];}max = sum * arr[popIndex] > max ? sum * arr[popIndex] : max;}return max;}
};

在这里插入图片描述
上面的代码还有可以优化的地方，就是先把前缀和存到一个数组中，需要累加和的时候直接取即可。

class Solution
{
public:int max(vector<int>& arr){int size = arr.size();vector<int> sum(size);sum[0] = arr[0];// 求前缀和for(int i = 1; i < size; ++i){sum[i] = sum[i - 1] + arr[i];}int ret = -1;stack<int> st;st.push(0);for(int i = 1; i < size; ++i){while(!st.empty() && arr[st.top()] >= arr[i]){int popIndex = st.top();st.pop();// 栈为空,说明popIndex左边没有比它小的数,累加和为sum[i-1]// 栈不为空,说明popIndex左边有比它小的数,累加和为sum[i-1] - sum[st.top()]int Sum = st.empty() ? sum[i - 1] : (sum[i - 1] - sum[st.top()]);ret = ret > (Sum * arr[popIndex]) ? ret : (Sum * arr[popIndex]);}st.push(i);}while(!st.empty()){int popIndex = st.top();st.pop();// 在栈中的元素,右边没有比它们小的元素了// 栈为空,说明popIndex左边没有比它小的数,累加和为sum[size-1]// 栈不为空,说明popIndex左边有比它小的数,累加和为sum[size-1] - sum[st.top()]int Sum = st.empty() ? sum[size - 1] : (sum[size - 1] - sum[st.top()]);ret = ret > (Sum * arr[popIndex]) ? ret : (Sum * arr[popIndex]);}return ret;}
};