4.单调栈，单调队列

1.单调栈

https://www.starrycoding.com/problem/60
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5+9;
ll a[N],l[N];

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	ll n;cin >> n;
	for(int i = 1;i <= n;++i) cin >> a[i];
	
	stack<int> stk;
	
	for(int i = 1;i <= n;++i)
	{
		while(stk.size() && stk.top() >= a[i]) stk.pop();
		if(stk.empty()) l[i] = -1;  
		else l[i] = stk.top();
		stk.push(a[i]);
	}
	
	for(int i = 1;i <= n;++i) cout << l[i] << ' ';
}

2.单调队列

//https://www.starrycoding.com/problem/61
#include<bits/stdc++.h>
using namespace std;
using ll = long long ;
const int N = 2e5+9; 
ll a[N];

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	ll n,k;cin >> n >> k;
	for(int i = 1;i <= n;++i) cin >> a[i];
	
	deque<int> dq;
	//求最大
	for(int i = 1;i <= n;++i)
	{
		//队头合法性
		while(dq.size() && dq.front() <= i-k)dq.pop_front();
		//队尾优越性
		while(dq.size() && a[dq.back()] <= a[i]) dq.pop_back();
		
		dq.push_back(i);
		
		if(i >= k) cout << a[dq.front()] << ' ';
	}
	cout << '\n';
	dq = deque<int>();
	
	for(int i = 1;i <= n;++i)
	{
		//队头合法性
		while(dq.size() && dq.front() <= i-k)dq.pop_front();
		//队尾优越性 
		while(dq.size() && a[dq.back()]>= a[i]) dq.pop_back();
		
		dq.push_back(i);
		
		if(i >= k) cout << a[dq.front()] << ' ';
	}
	
}