《剑指Offer》 面试题30 包含min函数的栈

题目描述

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。

源代码

class Solution {
public:
    //min保证当栈中的元素pop后 最小的元素是现在栈中最小的元素 如果pop出去的那个元素是之前栈最小的元素，那么现在，最小的元素就发生变化了
    void push(int value) {
        st.push(value);
        if (!minSt.empty()) {
        int min = minSt.top();
        if (value >= min) {
            minSt.push(min);
        } else {
            minSt.push(value);
        }
        } else {
            minSt.push(value);
        }
    }
    void pop() {
        int top = st.top();
        st.pop();
        minSt.pop();
    }
    int top() {
        int top = st.top();
        return top;
    }
    int min() {
        int top = minSt.top();
        return top;
    }
    private:
    stack <int> st;
    stack <int> minSt;
};