简介

单调栈，即满足单调性的栈。

基本思想

在每次插入时使栈保持单调性即可。

例题

【模板】单调栈

大致模板

int n;
std::vector<int> a(n+3), ans(n+3);
std::stack<int> sta;
for(int i = n; i > 0; --i) {
  for(; !sta.empty() && a[sta.top()] <= a[i]; ) // <= 可以根据需求改成不同符号
    sta.pop();
  if(sta.empty()) 
    ans[i] = 0;
  else ans[i] = sta.top();
  sta.push(i);
}