【题目/算法训练】：单调队列&&单调栈

🚀 前言：

【算法】单调队列&&单调栈 可以在看完这篇文章后，再来写下面的题目

一、绝对差不超过限制的最长连续子数组

思路：

      1） 就相当于滑动窗口，维护滑动窗口内的两个值，一个是最大值，一个是最小值，如果当前滑动窗口的最大值和最小值的差值都不超过  limit ，说明滑动窗口内任意两个数的差值都不会超过  limit 。

       2）由于需要维护两个值 ，因此我们需要两个单调队列，同时维护一个区间的值，一个去维护最大值，一个去维护最小值。

       3） 由于要求最长连续子数组的长度，那么我们假设已经 有【l，r - 1】满足条件的最长子数组长度，然后尾指针向后移动一位，假设此时【l，r】的最大差值已经超过 limit，此时 l 应该向后移动,，这道题本质就是一个变长的滑动窗口，其长度是根据题目所给条件来进行调整。

class Solution {
public:
    int longestSubarray(vector<int>& nums, int limit) {
        //处理边界情况
        if (limit < 0) return 0;
      
        deque<int> min_q, max_q;
        int l = 0, ans = 1 ;
        min_q.push_back(0);
        max_q.push_back(0);

        for (int r = 1, n = nums.size(); r < n; r++) {
            while (!min_q.empty() && nums[r] < nums[min_q.back()]) min_q.pop_back();
            while (!max_q.empty() && nums[r] > nums[max_q.back()]) max_q.pop_back();
            min_q.push_back(r);
            max_q.push_back(r);

            if (nums[max_q.front()] - nums[min_q.front()] > limit) {
                if (min_q.front() == l) min_q.pop_front();
                if (max_q.front() == l) max_q.pop_front();
                l++;
            }
            ans = max(ans, r - l + 1);
        }
        return ans;
    }
};

二、最大矩形面积

思路：

 1） 假设我们现在可以切割出的最大矩形面积为S;

 2）此时矩形高度等于其范围内最矮木板的高度。

 3）假设最大矩形两边各有1号和2号两块木板，此时1和2号的高度比矩形高度要小，

 4） 以每一块木板作为矩形最大高度的基准值，然后枚举去判断能够可以切出来的最大面积。因此我们需要求该木板左右两边最近的1，2号木板，就可以用单调栈。

#include<iostream>
#include <vector>
#include <cstdio>
#include <stack>
#include <algorithm>
#include <cstring>
using namespace std;

typedef long long ll;

int main()
{
	int n;
	cin >> n;
	vector<ll> arr(n + 2, -1);  //让最左边和最右边木板旁边还有木板
	vector<ll> l(n + 2), r(n + 2);//分别存储左右两边小于第i块木板的那个下标
	for (int i = 1; i <= n; i++) cin >> arr[i];
	
	stack<ll>s;
	for (int i = 1; i <= n + 1; i++) {
		while (!s.empty() && arr[i] < arr[s.top()]) {
			r[s.top()] = i;
			s.pop();
		}
		s.push(i);
	}
	while (!s.empty()) s.pop();
	for (int i = n; i >= 0; i--) {
		while (!s.empty() && arr[i] < arr[s.top()]) {
			l[s.top()] = i;
			s.pop();
		}
		s.push(i);
	}
	ll ans = 0;
	for (int i = 1; i <= n; i++) { //以每一块木板为基准值切出的最大面积
		ll height = arr[i], width = r[i] - l[i] - 1;
		ans = max(ans, height * width);
	}
	cout << ans << "\n";
	return 0;
}

三、接雨水

首先由题目可知只有凹形才能接雨水，因此我们假设已经存在1号柱子到2号柱子如下构成的绿色接雨水面积，当再来了一个3号柱子，我们又可以新接一些雨水，即黄色面积，假设1号柱子的下标为i，3号柱子的下标为j，此时黄色部分的长度为 j - i,高度为min (h3 - h1) -h2

因此我们不断往后增加柱子，比如4号柱子，那里又可以增加红色雨水面积，加入5号柱子，计算不出我们可以接雨水的面积，再增加6号（仍然没有新增雨水的量），再加入7号柱子，

此时h7和h5可以算出可以接雨水的量，此时可以当作h6不存在，如下图所示

因此可知我们应该需要维护的就是上图中h4、h5、h7这种单调递减的序列，然后每次在后面增加一个柱子，如果我们增加的柱子比我们最后的柱子要高，就可以形成新的雨水，然后计算增加雨水的量，进行累加即可，易知应该需要用到单调栈

class Solution {
public:
    int trap(vector<int>& height) {
        stack<int> s;
        int ans = 0;
        for (int i = 0; i < height.size(); i++) {
            while (!s.empty() && height[s.top()] < height[i])
            {
                int min_h = height[s.top()];//记录弹出柱子的高度
                s.pop();
                if (s.empty()) break;
        //计算出弹出柱子两侧相邻最矮柱子的高度与弹出柱子高度差，再乘以下标差，此时就为新增雨水面积
                ans = ans + (min(height[s.top()], height[i]) - min_h) * (i - s.top() - 1); 
            }
            s.push(i);
        }
        return ans;
    }
};

四、和至少为K的最短子数组

思路：

       假设如下每个节点都代表了前缀和数组中的每一个值，假设当前已经遍历到黄色这个节点，绿色代表黄色点之前所有点的最小值，红色点代表从绿色到黄色点区间内的最小值，蓝色点则代表红色点到黄色点区间内的最小值

       此时我们需要找到黄色点前的一个点，使得黄色点需要减去那一个值，并且这个差值必须大于等于K，因此我们需要找的就是黄色点前的最小值，假如黄色点减去绿色点的差值大于等于K，但是由于我们要求最短子数组，此时绿色点就可以被抛弃，即弹出，因此我们就需要在绿色点后面找点，即红色点，如果黄色点与红色点的差值也大于等于K，那么黄色点也弹出，那我们就去找蓝色点，不断往后，即需要维护绿红蓝这三个点

        易知应该使用单调队列来解决该题，即把原数组处理为前缀和数组，然后将原数组中每一项依次性压入到单调队列中，每次压入前，需要用当前的值和单调队列的队首进行比较，若当前值减去队首元素的值大于等于K，此时队首元素就可以出队，然后再把当前元素压入单调队列

class Solution {
public:
    int shortestSubarray(vector<int>& nums, int k) {
        int n = nums.size();
        vector<long long> s(n + 1, 0);//前缀和数组
        for (int i = 1; i <= n; i++) {
            s[i] = s[i - 1] + nums[i - 1];
        }
        deque<int>q;
        q.push_back(0);
        int ans = n + 1;
        for (int i = 1; i <= n; i++) {
            while (!q.empty() && s[i] - s[q.front()] >= k) {
                ans = min(ans, i - q.front());
                q.pop_front();
            }

            while (!q.empty() && s[i] < s[q.back()]) q.pop_back();
            q.push_back(i);
        }

        if (ans == n + 1) return -1;
        return ans;
    }
};

五、双生序列

思路：

       假设已有A、B两序列，两个都固定了结尾位置r的情况下，它们的趋势相同就是从最小值到最小值后面的最小值到最小值后面的最小值的最小值的所在位置相同，然后将黄蓝绿红的位置存储在单调队列中，其趋势相同也意味着它们在单调队列所存储的元素也相同，注意在单调队列中所存储位置对应值应该是单调递增的

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <deque>
using namespace std;

int main()
{
	int n;
	cin >> n;
	vector<int> a(n + 1), b(n + 1);
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) cin >> b[i];
	deque<int> ap, bp;
	int p; //找最大值i
	for (p = 1; p <= n; p++)
	{
		while (!ap.empty() && a[p] <= ap.back()) ap.pop_back();
		while (!bp.empty() && b[p] <= bp.back()) bp.pop_back();

		ap.push_back(a[p]);
		bp.push_back(b[p]);

		if (ap.size() != bp.size()) break; //说明到此位置结束
	}

	cout << p - 1<< endl; 
	return 0;
}