把一个美元号改成两个美元号

$f(x)$

<font color = #82318E>单调栈和单调队列</font>

摘要

单调队列和单调栈，在普通的队列和栈基础上，要求元素单调，实际上单调队列和单调栈的应用也是基于其单调性的性质。

事实上，我认为这两种特殊的数据结构相差并不是太大（至少从下面的这几道例题来看）。假设我们都使用deque的push_back()来添加新元素，因为要满足单调性，就一定会有和back()比较并pop_back()的操作。正常来讲这是栈的操作(FIFO)，在队列里是不允许的，传统的队列只允许pop_front()。所以就发现，单调队列也需要类似栈的操作。

那么单调队列和单调栈都在什么时候用呢？事实上，对于单调队列来说，正因为他允许进行pop_front()操作，所以如果有限制一个长度，然后要求极大/极小值，应该就是单调队列。而如果是有一种求“最近的”那种感觉，那应该就是单调栈了。

• deque常用的函数有front(), back(), push_front(), push_back(), pop_front(), pop_back(), size(), empty()…

常见顺序容器的对比：

<font color = #82318E>单调栈</font>

• 单调栈：顾名思义，就是这个栈中的元素保持单调性（单调递增或单调递减）

  利用单调性，取当前元素左边第一个比他大/小的元素比较方便（就是和当前元素相临最近的比他大/小的元素）

• 维护单调栈的思路：当前元素和栈顶元素比较，若栈顶元素大于当前元素，栈顶元素出栈；重复处理，直到占栈空或栈顶元素小于当前元素（单调递增栈）

$Example -1$  查询…

• 问题分析：

  求左侧最近的一个比当前元素小的数，单调栈的典型应用。

• 代码：

  （这道题是一道PPT上的题，因此代码就是单调栈的一个大概思路，不保证严谨性哦！）

#include <bits/stdc++.h>
using namespace std;
int num[100];
deque<int> de;//单调栈
int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
		scanf("%d", &num[i]);
	for (int i = 1; i <= n; i++) {
		//把栈顶元素与当前元素做比较，确保加入当前元素后栈的单调性
		//(若栈不空)取栈顶元素，就是和当前元素相临最近的比当前元素小的值
		//将当前元素入栈
		while(!de.empty()&&num[de.back()]>num[i])
			de.pop_back();

		if(de.empty()) printf("-1");
		else printf("%d", num[de.back()]);

		de.push_back(i);

		if(i!=n) printf(" ");
	}//for
}

$Example -2$ 幸福指数

（Ps：这是上学期数据结构上机实验的一道题，在外面应该是找不到一模一样的OJ）

• 问题分析：

  怎么求幸福值呢？很自然会想，先确定区间$[l,r]$，然后找到区间内的最小值，求出幸福值。这种思路就是纯暴力了，没有技巧，时间复杂度 $O(n^2)$ .

  我们不妨换一个思路：先确定一个数 $a_i$ ，之后找到区间 $[l_i,r_i]$ ，让 $a_i$ 成为这个区间内的最小值。如何根据 $a_i$ 求出区间 $[l_i,r_i]$ 呢？

  <font color = #82318E>我们在 $a_i$ 左侧找一个数 $l_i’$ ，他是与 $a_i$ 距离最近的一个 $ <a_i $ 的数；再在 $a_i$ 右侧找一个数 $r_i’$ ，也是与 $ a_i $ 距离最近的一个 $ a_i $ 的数。可以得出，$l_i’$ 到 $ r_i’$ 这个区间（不包括$l_i’,r_i’$）的数字中，$a_i $ 是最小的。这里应该有一个简单的证明，但是很好像明白，就略了。</font>

  因此，$l_i,r_i$分别是$l_i’$ 后面的那个数和$ r_i’$ 前面那个数，这样区间我们就大致确定了。但是还有一些细节需要仔细考虑的：

  • 首先要注意这个$l_i’$ 和 $ r_i’$ 是 $ <a_i $ 还是 $ \leq a_i $ ，因为可能会有连续重复的数字。

    例如...0 6 6 6 6 6...，这里有5个6，假如要判断第3个6的左侧区间，如果是$\leq$，左区间就是第2个6；如果是$<$左区间就是最前面的那个6。我们想让区间长一些，这样区间sum会更大，因此是 $ <a_i$。

    在编程的时候，这里会体现在维护单调栈时判断 while (!de.empty() && num[de.back()]>=num[i])，这里是不可以>判断的！当然也可以大于号和大于等于都试一下，就知道那里对了。

  • 还要考虑到如果$a_i$的左侧没有比他小的元素，那他自己就是左边的边界。关于边界的处理方法，可以直接用if/else，也可以对边缘的num值(num[0]和num[n+1])进行巧妙处理，可以参考第二个代码。

  而求最相临的比当前元素小的值就是单调递增栈啦！所以就可以考虑写代码了。正常来讲，单调栈的时间复杂度为$O(n)$.

• 需要注意的问题：
  1. 在比较当前元素和栈顶元素时，应该是用>=而不是>
  2. 认真读题，要注意“如果有多个这样的区间，输出最长最左区间”这句话。这里整整占了 $40$ 分！考虑区间长度要细致，$\alpha$到$\beta$的区间长度是$\beta-\alpha+1$.结合具体问题考虑（细节见注释）
• 我的代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MaxN = 1e5+5;
const int inf = 0x3f3f3f3f;
deque<ll> de;
ll num[MaxN], sum[MaxN], qian[MaxN], hou[MaxN];
//num用来存数字，sum[i]是前i个数的前缀和
//qian/hou分别是与第i个元素两边的区间，是通过单调栈求出来的
//你可以直接在这两个数组中保存最邻近比当前元素小的下标
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &num[i]);
        sum[i] = sum[i-1]+num[i];
    }
    //单调栈
    for (int i = 1; i <= n; i++) {
        //先正着来一遍
        while (!de.empty() && num[de.back()]>=num[i])
            de.pop_back();
        //(栈非空时)此时栈顶元素就是最邻近比当前元素小的值(下标)
        if (de.empty()) qian[i] = 1;
        else qian[i] = de.back()+1;//进行了分情况的讨论
        de.push_back(i);
    }
    while (!de.empty()) de.pop_back();
    for (int i = n; i >= 1; i--) {//错误1 这里写成i++
        //再反着来一遍
        while (!de.empty() && num[de.back()]>=num[i])
            de.pop_back();
        if (de.empty()) hou[i] = n;
        else hou[i] = de.back()-1;
        de.push_back(i);
    }
    //输出
    ll f,r,res=-inf;
    for (int i = 1; i <= n; i++) {
        ll a = qian[i]-1;
        ll b = hou[i];
        ll c = (sum[b]-sum[a])*num[i];
        if (res<c) res=c,f=a+1,r=b;
        else if (res==c && (b-a)>(r-f+1)) f=a+1,r=b;
        //这里真是个大坑...最开始忘记考虑了60分，后来用(b-a)和(r-f)进行比较，然后80分
        //但实际上区间x到y元素到个数应该是y-x+1
        //因为b-a已经包含一个1了(实际上是因为计算区间sum需要令a=qian[i]-1) 因此这里不用+1
        //但是r-f需要加1！
        //当然，如果你直接用hou[i]-qian[i]和r-f进行比较可能没考虑这么细致也可以AC
        //这告诉了我们没事儿不要瞎设这么多字母（bushi
    }
    cout << res << endl << f << " " << r;
}

• 另一位大佬的代码：

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 5;
typedef long long ll;
ll sum[maxn];
int h[maxn],l[maxn],r[maxn];
int n;
ll ma, posl, posr;
stack<int> q;
int main() {
	scanf("%d", &n);
	h[0] = h[n+1] = -INF;
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &h[i]);
		sum[i] = sum[i-1] + h[i];
	}
	q.push(0);
	for (int i = 1; i <= n; ++i) {
		while (!q.empty() && h[q.top()] >= h[i]) q.pop();
		l[i] = q.top();
		q.push(i);
	}
	while (!q.empty()) q.pop();
	q.push(n+1);
	for (int i = n; i >= 1; --i) {
		while (!q.empty() && h[q.top()] >= h[i]) q.pop();
		r[i] = q.top();
		q.push(i);
	}
	ll tmp = 0; ma=0;
	for (int i = 1; i <= n; ++i) {
		tmp = (sum[r[i]-1] - sum[l[i]])*h[i];
		if (tmp > ma) {
			ma = tmp;
			posl = l[i]+1;
			posr = r[i]-1;
		}
		else if (tmp == ma) {
			if (posr-posl < r[i]-1-l[i]-1) {
				ma = tmp;
				posl = l[i]+1;
				posr = r[i]-1;
			}
		}
	}//for
	printf("%lld\n%lld %lld\n", ma, posl, posr);
}

<font color = #82318E>单调队列</font>

• 单调队列：一种特殊的队列，队列中的元素保持单调递增或单调递减

  利用单调性，单调队列的队首元素是连续一段数的最值/极值（例如：单调递增队列的队首就是最小值）

• 单调队列的维护：

  单调性维护：当前元素和队尾元素比较，若队尾元素大于当前元素，队尾元素出队；重复处理，直到队空或队尾元素小于当前元素；当前元素入队。（单调递增队列）

  区间的维护：若队首元素的位置不在区间内，则队首元素出队；重复处理，直到队首元素在区间内

• （单调队列还有一些其它应用，如优化动态规划）

$Example -1$ 区间m内的最小值

• 思路：

  要求<font color = #82318E>给定区间范围内最小值</font>，单调队列的典型应用。

• 代码：

  （这道题是PPT上的题，因此代码就是单调队列的一个大概思路，不保证严谨性哦！）

#include <bits/stdc++.h>
using namespace std;
int n,m;
int num[100];
deque<int> de;
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        scanf("%d",&num[i]);
        //当前元素和队列尾部的元素进行比较，保证单调性
        //当前元素入队
        //删去区间外的队首元素，维护区间
        while(!de.empty() && num[de.back()]>=num[i])
            de.pop_back();
        de.push_back(i);
        if(i<m) continue;
        while(i-de.front() >= m) de.pop_front();//下标做差维护区间
        printf("%d",num[de.front()]);
        if(i!=n) printf(" ");
    }
}

$Example -2$ 最喜爱的序列

（Ps：也是数据结构上机实验的一道题）

• 题目意思：

  求序列中一段连续数sum的最大值，限制了序列长度不大于m。

  （如果不限制序列长度，应该是另外的解法了，据说是DP，题目链接：P1115 最大子段和 - 洛谷）

• 思路：

  题目很好理解，想必这道题是要使用什么技巧来解决。

  首先，可以利用前缀和优化连续一段数字的和，从A到B的和（包括A,B）就是$sum[A]-sum[B-1]$ （注意一下这里的$B-1$），这个很容易想到。

  接下来就是如何求解了。<font color = #82318E>我们可以让i从1到n遍历一遍，把第i个数字当作一段连续数字的末端，之后去找第j个数字（$j\leq i$），使得从j到i这段数字的和最大。</font>

  <font color = #82318E>用sum数组表示上面的说法就更简单了：已知sum[i]，找一个j，使得sum[i]-sum[j-1]最大。因为这时sum[i]的值可以理解成是一个固定的值，所以想知道j，就要保证sum[j-1]和sum[i]相差最大。因为题目中限制了范围m，所以sum[j-1]就是这段范围内的极小值。这样，我们就把问题转化成了单调队列求解的sum数组中区间m内的最小值问题。</font>

• 代码：

    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int inf = 0x3f3f3f3f;
    const int MaxN = 5e5+5;
    ll sum[MaxN];
    int n,m,f,r;
    deque<ll> de;
    int main() {
        cin >> n >> m;
        for (int i = 1; i <= n; i++) {
            scanf("%lld",&sum[i]);
            sum[i] += sum[i-1];
        }
        ll res = -inf;
        for (int i = 1; i <= n; i++) {//单调队列部分
            while (!de.empty() && sum[de.back()]>sum[i])//维护单调性
            	de.pop_back();
            de.push_back(i);
            while (de.back()-de.front() >= m)//维护区间
            	de.pop_front();
            if (sum[de.back()]-sum[de.front()-1] > res
            || (sum[de.back()]-sum[de.front()-1]==res)&&(de.front()<f)) {
            	res = sum[de.back()]-sum[de.front()-1];
            	f = de.front();
            	r = de.back();
            }//20,22,23,24,26行的de.back()可以换成i
        }
        cout << res << " " << f << " " << r;
    }
  

• 扩展：

  简单的二维前缀和（我自己起的名字，不过好像也确实有）。在水CSP第二题的时候遇到的。题目是：202104-2 邻域均值。

  这道题是要重复对二维的矩阵进行加法运算，如果暴力写的话只能70分，所以要在求和的地方进行优化。

  我自己的办法是定义一个二维的前缀和，具体说明如下：

  $sum[m][n]$ 代表前m行n列的矩阵的元素和。

  输入时计算的方法：$sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]$ （大概就是先加了两个矩阵的和，再减去加重了的部分）

  计算左上角坐标为$(a,b)$，右下角坐标为$(c,d)$的矩阵的和：$sum[c][d]-sum[a-1][d]-sum[c][b-1]+sum[a-1][b-1]$ （方法和输入时的思路是一样哒）

  这里一定要画一个示意图，加深一下理解（注意一下下标-1的地方）

  这样优化之后，就可以比较容易地完成这个题了。