单调栈

  • 单调栈是满足单调性的栈结构。与单调队列相比，其只在一端进行进出。
  • 单调递增栈：单调递增栈就是从栈顶到栈底数据单调递增
  • 单调递减栈：单调递减栈就是从栈顶到栈底数据单调递减

实现

  • 单调递减栈的实现例子。
1
2
3
4
5
6
7
8
9
10
11
stack<int> st;
// 单调递减栈的插入
void insert(int x)
{
	// 如果当前元素比栈顶元素小则弹栈维护单调性质（栈顶->栈底：大->小）
	while(!st.empty() && x<st.top()) {
		st.pop();
	}
	// 插入元素
	st.push(x);
}

应用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> dailyTemperatures(vector<int>& temperatures) {
	vector<int> ans(temperatures.size());
	stack<int> st;
	// 从后往前构建单调递减栈
	for(int i=temperatures.size()-1;i>=0;i--) {
		// 如果栈顶比当前要小，弹出
		while(!st.empty() && temperatures[i]>=temperatures[st.top()]) {
			st.pop();
		}
		// 此时栈里剩下的就是要找的元素
		if(st.empty()) ans[i] = 0;
		else ans[i] = st.top()-i;
		st.push(i);
	} 
	return ans;
}

例题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
#define ll long long
#define fupe(i,a,b) for(int i=a;i<=b;i++)
#define fdowne(i,a,b) for(int i=a;i>=b;i--)
#define fup(i,a,b) for(int i=a;i<b;i++)
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin>>n;
    vector<int> h(n),v(n),e(n);
    fup(i,0,n) cin>>h[i]>>v[i];
    stack<int> st;
    // 从后往前构建单调递增栈，依次获取第一个大于该元素的元素下标(该元素右侧)
    fdowne(i,n-1,0)
    {
        while(!st.empty() && h[i]>=h[st.top()]){
            st.pop();
        }
        if(!st.empty()) {
	        // 更新能量值,此时栈顶就是要找的那个位置。
            e[st.top()]+=v[i];
        }
        st.push(i);
    }
    while(!st.empty()) st.pop();
    // 从前往后构建单调栈，依次获取第一个大于该元素的元素下标(该元素左侧)
    fup(i,0,n)
    {
        while(!st.empty() && h[i]>=h[st.top()])
        {
            st.pop();
        }
        if(!st.empty()) {
	        // 更新能量值,此时栈顶就是要找的那个位置。
            e[st.top()]+=v[i];
        }
        st.push(i);
    }
    int ans = 0;
    fup(i,0,n) ans= max(ans,e[i]);
    cout<<ans;
    return 0;
}

单调队列

  • 顾名思义，就是有某种单调性的队列，分为单调递增队列和单调递减队列。

构建

  • 为了维护队列的单调性，当新元素进入队尾时，比较新元素与队尾元素的大小，如违反单调性，则弹出队尾元素，重复到队列为空或符合单调性为止。
  • 如果是要维护滑动窗口的性质，则需检查队首元素是否在滑窗内，若不处于滑窗内则需出队。
  • 最后将新元素入队。

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
int q[N]; // 单调递增队列的实现
int head=0;int tail=-1;
// 枚举滑动窗口右端点
for(int i=0;i<n;i++) {
	// 若新元素比队尾元素小，则弹出队尾元素
	while(head<=tail && a[i]<=a[q[tail]]) tail--;
	// 若队首元素不在滑窗内，队首出队
	while(head<=tail && i-q[head]+1>k) head++;
	// 新元素入队
	q[++tail] = i;
	// 队首元素即滑动窗口内最小值的下标
	if(i>=k-1) ansmin[i-k+1] = a[q[head]];
}

例题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 1e6+5;
int n,k;
int a[N];
int q[N];
int head=0;int tail=-1;
int ansmin[N];
int ansmax[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>k;
    for(int i=0;i<n;i++) cin>>a[i];
    // 枚举滑动窗口右端点
    for(int i=0;i<n;i++) {
        // 若新元素比队尾元素小，则弹出队尾元素
        while(head<=tail && a[i]<=a[q[tail]]) tail--;
        // 若队首元素不在滑窗内，队首出队
        while(head<=tail && i-q[head]+1>k) head++;
        // 新元素入队
        q[++tail] = i;
        // 队首元素即滑动窗口内最小值的下标
        if(i>=k-1) ansmin[i-k+1] = a[q[head]];
    }
    for(int i=0;i<n-k+1;i++) cout<<ansmin[i]<<" ";
    cout<<'\n';
    // 清空队列
    head=0,tail=-1;
    // 枚举滑动窗口右端点
    for(int i=0;i<n;i++) {
        // 若新元素比队尾元素大，则弹出队尾元素
        while(head<=tail && a[i]>=a[q[tail]]) tail--;
        // 若队首元素不在滑窗内，队首出队
        while(head<=tail && i-q[head]+1>k) head++;
        // 新元素入队
        q[++tail] = i;
        // 队首元素即滑动窗口内最大值的下标
        if(i>=k-1) ansmax[i-k+1] = a[q[head]];
    }
    for(int i=0;i<n-k+1;i++) cout<<ansmax[i]<<" ";
    return 0;
}
  • P2698 Flowerpot S - 洛谷
  • 按坐标排序后，题意可化为求最小的区间长度d，使得该区间内的最大值与最小值之差大等于D，且当区间左端点l固定时，右端点向右扩展的同时，最大值只会越来越大，最小值只会越来越小，所以f(r) = MAX[L,R] - MIN[L,R]是单调递增的，左端点固定时，第一个满足条件的右端点就是该左端点的最优答案，此时更新答案，并将左端点向右移动。此题便转化为不定长滑动窗口问题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <vector>
#include <algorithm>

#define ll long long
using namespace std;

const int N = 1e5+5;
int n,d;

int q1[N]; // 维护区间max , >单调递减
int q2[N]; // 维护区间min , <单调递增
int head1=0,tail1=-1;
int head2=0,tail2=-1;
int ans = 0x3f3f3f3f;
int leftpos=0;

struct drop{
    int x;
    int t;
    bool operator<(drop& b) {
        return x<b.x;
    } // 便于排序
};

vector<drop> drops;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>d;
    drops.resize(n);
    for(int i=0;i<n;i++) {
        cin>>drops[i].x>>drops[i].t;
    }
    sort(drops.begin(),drops.end()); // 按坐标排序

	// 逐渐扩展区间右端点
    for(int right=0;right<n;right++) {
	    // 入队
        while(head1<=tail1 && drops[right].t>=drops[q1[tail1]].t) tail1--;
        q1[++tail1] = right;
        while(head2<=tail2 && drops[right].t<=drops[q2[tail2]].t) tail2--;
        q2[++tail2] = right;
		
		// 满足条件则更新答案
        while(leftpos<=right && drops[q1[head1]].t - drops[q2[head2]].t>=d) {
            ans = min(ans,abs(drops[q1[head1]].x - drops[q2[head2]].x));
            // 缩小窗口
            leftpos++;
            while(head1<=tail1 && q1[head1]<leftpos) head1++;
            while(head2<=tail2 && q2[head2]<leftpos) head2++;
        }
    }
    if(ans==0x3f3f3f3f) cout<<-1;
    else cout<<ans;
    return 0;
}