在栈中实现min函数

在《剑指Offer》一书看到的题目。要求push, pop, min的时间复杂度都为O(1)

一开始我能想到的方法是，用一个指针指向当前栈中最小的元素，当有新元素进来时， 和当前最小元素比较，如果较小则更新指针，否则不做更改。但是当元素出栈时，就出现 问题了，如果出栈的是最小的那个元素，那我这个指针应该指向哪里呢？

再想，如果我用2个指针，一个指向次小元素，一个指向最小元素，会怎样呢？其实也不行， 这样是换汤不换药，当最小元素出栈时，次小元素也不知道指向哪里？

没办法，我记录所有元素的顺序就行了。这样的话，空间复杂度会翻倍，但是这是让3个 函数时间复杂度都为O(1)以空间换时间的办法。

实际上这里涉及到 状态 的概念。当栈中只有一个元素时是一个状态，加了一个元素 之后，又是一个状态，而我们要维护每个状态时的最小值，放到另外一个栈中，那么当元素 出栈时，另外一个栈中存放的最小值也出栈就行了。

直接用 std::stack 来写两个内部栈，随手写了份代码。

::: {.code-include lexer="cpp"} ./add-min-function-to-stack.cc :::