单调栈

定义

单调栈是满足单调性的栈数据结构，栈内元素始终保持单调递增或单调递减。它通过在入栈时维护这种单调性，能够高效地解决一类“寻找下一个更大/更小元素”的问题。

模版

寻找下一个更大元素 (Next Greater Element)

int N, nums[N], right[N];
stack<int> s; // 存储元素下标
 
void next_greater_element()
{
	for(int i = 1; i <= N; i++)
	{
		while(!s.empty() && nums[s.top()] < nums[i]) // 找出栈中所有小于num[i]的元素
		{
			right[s.top()] = i; // 第i个元素即为第s.top()的下一个更大元素
			s.pop(); // 继续处理下一个
		}
		s.push(i); // 此时要么栈为空，要么栈顶元素大于等于第i个元素
	}
	while(!s.empty()) // 如果剩下没有找到更大元素的元素
	{
		right[s.top()] = N + 1; // 右边没有更大元素，设置为N + 1
		s.pop();
	}
}

寻找下一个更小元素 (Next Smaller Element)

int N, nums[N], right[N];
stack<int> s; // 存储元素下标
 
void next_smaller_element()
{
	for(int i = 1; i <= N; i++)
	{
		while(!s.empty() && nums[s.top()] > nums[i]) // 找出栈中所有大于num[i]的元素
		{
			right[s.top()] = i; // 第i个元素即为第s.top()的下一个更小元素
			s.pop(); // 继续处理下一个
		}
		s.push(i); // 此时要么栈为空，要么栈顶元素小于等于第i个元素
	}
	while(!s.empty()) // 如果剩下没有找到更小元素的元素
	{
		right[s.top()] = N + 1; // 右边没有更小元素，设置为N + 1
		s.pop();
	}
}