关于单调栈
目录
- 概述
- 实现
- 思想
- 例一 P5788 [模版]单调栈
- 例二 P4147 玉蟾宫
Part 1 概述
单调栈是一种其中元素具有单调性的线性结构。
由于其栈的特性,这种结构可以用来处理左边\右边比它小\大的数。
实际上,作者认为,遇到题目中元素:
- “限制”它的左、右且被其左、右“限制”的
- 限制具有可比较、可累加的性质时
- 不满足单调时前面元素无效
应该考虑能否使用单调栈进行优化。
单调栈的思想十分巧妙,我们待会在p3中探讨。
Part 2 实现
单调栈没有特别固定的实现方式,但是基本结构是:
stack<int> st;
for(){
int x;
//获取当前进栈元素,例如cin>>x;
if(x满足某些特征例如x>st.top()...){//如果满足单调性
st.push(x);
//...
}
while(!st.empty()&&x不满足上面特征例如x<=st.top()...){//如果不满足单调性,维护
st.pop();
//...
}
//...
}
Part 3 思想
作者概括,该算法思想是:"抛弃无用,合并相同"
蓝皮书说:
借助单调性处理问题的思想在于即使排除不可能的选项,保持策略集合的高度有效性和秩序性。