DP优化（一）单调队列/单调栈优化实例讲解

一、什么是单调栈和单调队列？

（1）单调栈

从名字上就听的出来，单调栈中存放的数据应该是严格单调有序的，具有以下两个性质。

1. 满足从栈顶到栈底的元素具有严格的单调递增或单调递减性；

2. 满足栈的后进先出特性，即越靠近栈底的元素越早进栈。

单调栈也分为单调递增栈和单调递减栈。

1. 单调递增栈：单调递增栈就是从栈底到栈顶数据是从小到大

2. 单调递减栈：单调递减栈就是从栈底到栈顶数据是从大到小

单调栈的维护

如何维护一个单调栈？出栈很简单，与普通栈相同，关键操作是入栈。

具体进栈过程

1. 对于单调递增栈，若当前进栈元素为e，从栈顶开始遍历元素，把小于e或者等于e的元素弹出栈，直接遇到一个大于e的元素或者栈为空为止，然后再把e压入栈中。

2. 对于单调递减栈，则每次弹出的是大于e或者等于e的元素。

于一个元素a，如果栈空则直接入栈。否则比较a与栈顶元素。假设一个单调递增的栈，若a > 栈顶元素，则直接把a入栈，栈仍满足单调的性质。若a < 栈顶元素，则将栈顶元素出栈，直到满足a < 栈顶元素，此时将a入栈。

（2）单调队列

队列中元素之间的关系具有严格单调有序性，而且，队首和队尾都可以进行出队操作，只有队尾可以进行入队操作。因此，在单调队列中求最值十分容易。

单调队列与普通队列有些不同，因为右端既可以插入又可以删除，因此在代码中通常用一份数组和rear与rear两个指针来实现，而不是使用STL中的queue。如果一定要使用STL ，那么则可以使用双端队列（即两端都可以插入和删除），即deque 。

队列的大小问题

在谈及单调栈时，无需关心栈的大小。而对于队列，队列的大小就很重要了。如果队列满了，我们的解决方法是，将队列头的元素弹出，再添加新的元素到队列尾。

单调队列的维护

具体入队过程

1. 对于单调递增队列，设当前准备入队的元素为e，从队尾开始把队列中的元素逐个与e对比，把比e大或者与e相等的元素逐个删除，直到遇到一个比e小的元素或者队列为空为止，然后把当前元素e插入到队尾。

2. 对于单调递减队列也是同样道理，只不过从队尾删除的是比e小或者与e相等的元素。

（3）单调栈与单调队列

单调队列

1. 可以查询区间最值（不能维护区间k大，因为队列中很有可能没有k个元素）；

2. 优化DP，单调队列一般是用于优化动态规划方面问题的一种特殊数据结构，且多数情况是与定长连续子区间问题相关联。

单调栈

1. 左边区间第一个比它小的数，第一个比它大的数

2. 确定这个元素是否是区间最值

3. 右边区间第一个大于它的值

4. 到右边区间第一个大于它的值 的距离

5. 确定以该元素为最值的最长区间

相同点：

1. 单调队列和单调栈的“头部”都是最先添加的元素，“尾部”都是最后添加的元素。

2. 递增和递减的判断依据相同：从栈底（队尾）到栈顶（队首），元素大小的变化情况。所以队列和栈是相反的。

3. 两者维护的时间复杂度都是O(n)，每个元素都只操作一次。

不同点：

1. 单调队列可以从队列头弹出元素，可以方便地根据入队的时间顺序（访问的顺序）删除元素。

2. 单调队列和单调栈维护的区间不同。当访问到第i个元素时，单调栈维护的区间为[ 0 , i )，而单调队列维护的区间为( lastpop , i ) 

3. 单调栈无法获取[ 0 , i )的区间最大值/最小值。因为单调队列可以访问“头部”和“尾部”，而单调栈只能访问栈顶（也就是“尾部”）。

二、单调队列/单调栈优化

例题一：单调队列优化

题目描述： 有 n 头奶牛在一排，每头奶牛的价值为 vi ，你可以选择若干头奶牛，但不能选择超过 k 头连续的奶牛。求价值之和最大为多少。n<=1e5

状态设置： f [ i ] ：选择了若干头牛，最后一头牛是第 i 头牛的最大价值。

问题分析： 显然，[ i − k , i − 1 ] 中有一头牛不能选，我们可以枚举这头牛的位置。

转移方程：f [ i ] = max ( f [ j − 1 ] + sum [ i ] − sum [ j ] ) ， j ∈ [ i − k , i − 1 ] 

时间复杂度：

单调队列优化

f [ i ] = max ( f [ j − 1 ] − sum [ j ] ) + sum [ i ]， j ∈ [ i − k , i − 1 ] 

g [ i ] = f [ i − 1 ] + sum [ i ] ，维护 g [ i ] 的区间最大值即可。

补充： 其实可以直接用线段树维护区间最值，时间复杂度 O(nlogn)

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
long long f[N];//表示选择了若干头牛，最后一头牛是第 i 头牛的情况下，的最大价值 
long long g[N];//g[i]=f[i-1]-sum[i] 
long long sum[N],a[N],que[N],head,rear;
int main(){
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum[i]=sum[i-1]+a[i]; 
	}
	long long ans=sum[1];
	f[1]=sum[1];
	g[0]=0;
	g[1]=-sum[1];
	que[rear++]=0;
	que[rear++]=1;
	for(int i=2;i<=n;i++){
		while(head<rear&&i-que[head]>k)head++;//维护范围限制 
	    f[i]=g[que[head]]+sum[i];//状态转移 
		g[i]=f[i-1]-sum[i];//计算新的要维护的值 
		while(head<rear&&g[i]>g[que[rear-1]])rear--;//加入新的要维护的值 
		que[rear++]=i;
		
		ans=max(ans,f[i]); 
	} 
	cout<<ans;
}

这块需要大家多多练习，才能更好的灵活运用。