int tt = 0;
for (int i = 1; i <= n; i ++ )
{
while (tt && check(stk[tt], i)) tt -- ;
stk[ ++ tt] = i;
}
这段代码是一个单调栈的实现,用于解决一些区间问题。
初始化栈为空,栈顶指针为0
。
遍历区间内的所有元素(假设区间范围为[1,n]),依次将它们压入栈中。
在每次插入新元素i
之前,先判断当前栈顶元素是否需要弹出。如果需要,则一直弹出,直到栈为空或者当前元素不再满足条件。这里check
函数是一个自定义的判断函数,用于判断当前元素i和栈顶元素stk[tt]
之间的关系。如果check
返回true
,则说明stk[tt]
可以被弹出。
将新元素i
压入栈中,并更新栈顶指针tt
。 这段代码的核心思想是维护一个单调递增(或递减)的栈,在遍历过程中不断将不符合要求的元素弹出,从而得到符合要求的最大(或最小)值。常见应用包括求解区间最大/最小值、计算某个数左右第一个比它大/小的数等问题。