模板 | 单调栈求左右节点邻近最小值

适用样例：

     给出长度为n的数组a,求数组中每个节点左右出现的第一个比该节点小的下标。

样例输入：n:5，a={1,4,2,3,5}。

输出结果：

代码详解：

     本题用单调栈进行求解，当进行遍历时，可知当出现栈顶比当前节点大时，说明当前节点就是右边第一个比栈顶小的，用样例模拟：

代码如下：

		//当栈不为空且节点小于栈顶时 
		while(!q.empty() && a[q.top()]>a[i])
		{
			int now=q.top();
			//此时a[q.top()]>a[i]，说明该节点是所有能弹出节点第一个比他小的值 
			r[now]=i;
			q.pop();
		}
		q.push(i);

     在确定右端值后，怎么确定左端值呢，通过样例可以发现弹出的节点是大于此时的栈顶的，毕竟栈是从大到小排的，所以弹出节点的后的栈顶，即为弹出节点的左端值。

		//当栈不为空且节点小于栈顶时 
		while(!q.empty() && a[q.top()]>a[i])
		{
			int now=q.top();
			//此时a[q.top()]>a[i]，说明该节点是所有能弹出节点第一个比他小的值 
			r[now]=i;
			q.pop();
			//栈中从小到大排序，所以弹出节点的左节点就是他第一个比他小的值 
			if (!q.empty())l[now]=q.top();
		}
		q.push(i);

     继续模拟样例：

     此时我们会发现当样例从小到大排时，栈无法弹出，所以需要在遍历结束后添加一段检验栈是否为空的代码。

//当出现节点一直从小到大排序时，栈不会为空 
	while(!q.empty())
	{
		//弹出节点，此时遍历结束，说明剩余节点的右侧以不存在比他们小的值 
		int now=q.top();
		r[now]=0;
		q.pop();
		//当节点还有剩余，说明他的左侧存在比他小的节点 
		if (!q.empty())l[now]=q.top();
	}

     至此，就能得出模板代码为：

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6+10; 
int n;
int a[N];
int l[N],r[N];
stack<int>q;

int main() { 
	cin >>n;
	for (int i=1;i<=n;i++)cin >>a[i];
	//遍历节点 
	for (int i=1;i<=n;i++)
	{
		//当栈不为空且节点小于栈顶时 
		while(!q.empty() && a[q.top()]>a[i])
		{
			int now=q.top();
			//此时a[q.top()]>a[i]，说明该节点是所有能弹出节点第一个比他小的值 
			r[now]=i;
			q.pop();
			//栈中从小到大排序，所以弹出节点的左节点就是他第一个比他小的值 
			if (!q.empty())l[now]=q.top();
		}
		q.push(i);
	}
	//当出现节点一直从小到大排序时，栈不会为空 
	while(!q.empty())
	{
		//弹出节点，此时遍历结束，说明剩余节点的右侧以不存在比他们小的值 
		int now=q.top();
		r[now]=0;
		q.pop();
		//当节点还有剩余，说明他的左侧存在比他小的节点 
		if (!q.empty())l[now]=q.top();
	}
	for (int i=1;i<=n;i++)cout <<l[i]<<' '<<r[i]<<"\n"; 
    return 0;
}