单调栈模版

单调栈需要两个数组，一个值数组，一个模拟栈数组，拿一道题来举例。

模拟栈数组中存储下标，单调栈顾名思义单调增或者单调减，并不是索引单调增或者单调减，这意义，我们要的是索引对应的值单调增或者单调减，这道题中我们显然是要单调减。我们知道在单增的序列中当前值永远比左边的的大，那么依照题意我们要找到左边第一个比当前值大的数，然后它们之间有多少个数便是题目要求的答案，那左边第一个比当前值大的数和当前值是不是构成一个单调减序列，只要将两者下标相减即可。

代码如下。

int main() {int n,len=0;std::cin >> n;std::vectora(n + 1), b(n + 1);for (int i = 1; i > a[i];for (int i = 1; i  a[b[len]] && len)len--;if (len == 0)std::cout << i - 1 << '\n';else std::cout << i - b[len] - 1 << '\n';b[++len] = i;}return 0;}