题解 | #包含min函数的栈#

//好久没自己实现过一个栈了。topindex用来指向栈顶的下一个元素。细节处理要稍微注意一下。
//对于最小元素的记录，在入栈时可以随时更新，但出栈时不太好搞。
//有两种方案，一个是维护一个“历史记录”，记录此前min的历史值，出栈时回退历史值即可。这个需要额外的O(N)空间复杂度，但时间上是O(1)的。
//另一个方案就是我写的这种，出栈时重新遍历整个栈来找到min。无需额外空间，但需要O(n)的时间。
#include <climits>
class Solution {
public:
    void push(int value) {
        if (value<minelement) {
            minelement=value;
        }
        s[topindex++]=value;
    }
    void pop() {
        s[--topindex]=INT_MIN;
        int index=0;
        int newmin=INT_MAX;
        while (s[index]!=INT_MIN) {
            if(s[index]<newmin)
                newmin=s[index];
            index++;
        }
        minelement=newmin;
    }
    int top() {
        int result=s[topindex-1];
        return result;
    }
    int min() {
        return minelement;
    }
private:
    array<int,300>s={INT_MIN};
    int topindex=0;
    int minelement=INT_MAX;
};