岩之痕

题解

/ 注册

全部文章 / 题解（共1篇）

单调栈题解

单调栈 O(N) 两次遍历创建一个栈来存各个值的下标。从左往右扫描数组，在将A[i]加入栈之前，将所有大于等于A[i]的元素出栈，此时栈顶元素就是左侧第一个小于A[i]的数的下标，在记录答案之后将i入栈，继续向右扫描。在此操作下，栈中元素一直保持单调递增，故称单调栈。正确性证明：假设j <...

单调栈线段树莫队算法

2019-08-22

8 1099