数据结构

单调栈

单调栈除了满足普通栈的性质外,还满足: • 满足从栈顶到栈底的元素具有严格的单调性 • 假设我们维护的是一个单调递减的栈: • 若进栈的元素为x,栈顶元素为S[l] • 那么当x>=S[l]时弹出栈顶元素,直到x<S[l]为止,压入元素x

单调队列

满足从队列头到队列尾的元素具有严格的单调性 • 假设我们维护的是一个单调递减的队列: • 若进队的元素为x,队尾元素为Q[r] • 那么当x>=Q[r]时弹出队尾元素,直到x<Q[r]为止,加入元素x