栈进阶数据结构

一、栈维护最值

时间复杂度 O(1)；设置三个栈 A、B、C，其中 A栈存储原始数据，B、C栈分别维护栈中最小值和最大值:

// 进栈操作
A.push(x);
B.push(min(B.top(),x));
C.push(max(C.top(),x));
// 出栈操作
A.pop();
B.pop();
C.pop();

二、对顶栈

应用思想：始终在序列中间某个指定位置进行修改；
建立两个栈，A栈存储从序列开头到当前位置的这一段子序列，栈 B存储当前位置到序列结尾处的这一段子序列，二者都以当前位置那一端作为栈顶。
栈求 最大前缀和 时，用一个数组 f维护栈 A的最大前缀和；

// A的栈顶位置下标pA，使用数组模拟栈
// sum是A的前缀和数组
A.push(x);
sum[pA]=sum[pA-1]+A[pA];
f[pA] = max(f[pA-1],sum[pA]);

三、单调栈

单调栈算法：时间复杂度 O(N)，处理问题思想在于 及时排除不可能的选项，保持策略集合的高度有效性和秩序性
应用：需要维护一个单调的序列并且可以不断从一端插入或删除
典例：

思路分析:

// 数组模拟栈：往往更快一些
a[n+1] = p = 0;  // p为栈顶位置，初始为0
for(int i=1;i<=n+1;i++)
{
	if(a[i] > s[p]){ // 矩形高度大于栈顶高度时直接进栈
		s[++p] = a[i];
		w[p] = 1;
	}else{  // 否则依次比较、寻找不高于当前矩形的位置
		int width = 0;
		while(s[p] > a[i]){
			width += w[p];// 宽度叠加
			// 这里s[p]是当前栈顶的高度值，ans记录最终的最大值
			ans = max(ans, (long long)width*s[p]); 
			p--;
		}
		// 更新栈，基于当前栈顶位置
		s[++p] = a[i],w[p] = width + 1;
	}
}