最大栈

最大栈

维护另一个栈 X，其中元素为 S 中该元素至栈底的最大值。 可以只保存不同的元素，X 中元素增加一个计数器得到 Y。

• 入栈时，检测当前值和栈顶元素值，若当前值较小，直接增加计数器，若栈顶元素值较小，将当前元素入栈。
• 出栈时，若栈顶元素计数器大于 1，则自减，若为 1，则出栈。 时间复杂度均为 $O(1)$。