美文网首页数据结构和算法
剑指offer - 包含min函数的栈

剑指offer - 包含min函数的栈

作者: Longshihua | 来源:发表于2019-08-06 09:10 被阅读0次

    题目

    定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素min函数。在该栈中,调用min、push及pop的时间复杂度都是O(1)

    思路

    建立辅助栈存储每次的最小元素

    分析

    1.jpg
    • 首先往空的数据栈里压入数字3,显然现在3是最小值,同时也把最小值3压入辅助栈
    • 接下来往数据栈里压入数字4,由于4大于之前的最小值,因此我们仍然往辅助栈里压入3
    • 继续往数据栈里压入数字2,由于2小于之前的最小值3,因此把最小值更新为2,并把2压入辅助栈。入栈数字1同理
    • 当最小元素从数据栈被弹出之后,同时弹出辅助栈的栈定元素,此时辅助栈的新栈定元素就是下一个最小值。比如,第五步的时候,弹出了最小值1,所以辅助栈新的最小值为2,其余操作同理

    算法实现

    定义模版栈类

    #include <iostream>
    #include <stack>
    #include <assert.h>
    
    using namespace std;
    
    template <typename T> class StackWithMin {
    public:
        StackWithMin() {}
        virtual ~StackWithMin() {}
    
        T& top();
        const T& top() const;
    
        void push(const T& value);
        void pop();
    
        const T& min() const;
    
        bool empty() const;
        size_t size() const;
    
    private:
        stack<T> m_data;
        stack<T> m_min;
    };
    
    // 入栈元素
    template <typename T>
    void StackWithMin<T>::push(const T& value) {
        m_data.push(value);
    
        if (m_min.size() == 0 || value < m_min.top()) {
            m_min.push(value); // 当前value入辅助栈
        } else {
            m_min.push(m_min.top()); 
        }
    }
    
    // 出栈元素
    template <typename T>
    void StackWithMin<T>::pop() {
        assert(m_data.size() > 0 && m_min.size()>0);
    
        m_data.pop();
        m_min.pop();
    }
    
    // 获取最小元素
    template <typename T>
    const T& StackWithMin<T>:: min() const {
        assert(m_data.size() > 0 && m_min.size() > 0);
    
        return m_min.top();
    }
    
    template <typename T>
    T& StackWithMin<T>::top() {
        return m_data.top();
    }
    
    // 获取顶部元素
    template <typename T>
    const T& StackWithMin<T>::top() const {
        return m_data.top();
    }
    
    // 是否为空
    template <typename T>
    bool StackWithMin<T>::empty() const {
        return m_data.empty();
    }
    
    // 栈大小
    template <typename T>
    size_t StackWithMin<T>::size() const {
        return m_data.size();
    }
    

    上面的实现每次都为辅助栈压入一个最小值,其实也可以只压入最小元素,但是在出栈的时候要判断两个栈的栈定元素是否相同,相同即出栈

    // 入栈元素
    template <typename T>
    void StackWithMin<T>::push(const T& value) {
        m_data.push(value);
        // 只入栈当前最小value
        if (m_min.size() == 0 || value <= m_min.top()) { // 注意=号,出栈需要
            m_min.push(value); 
        }
    }
    
    // 出栈元素
    template <typename T>
    void StackWithMin<T>::pop() {
        assert(m_data.size() > 0 && m_min.size()>0);
    
        if (m_min.top() == m_data.top()) { // 当栈定元素一样,辅助栈才出栈
            m_min.pop();
        }
        m_data.pop();
    }
    

    简单使用

    void Test(const char* testName, const StackWithMin<int>& stack, int expected) {
        if(testName != nullptr)
            printf("%s begins: ", testName);
    
        if(stack.min() == expected)
            printf("Passed.\n");
        else
            printf("Failed.\n");
    }
    
    int main(int argc, const char * argv[]) {
        StackWithMin<int> stack;
    
        stack.push(3);
        Test("Test1", stack, 3);
    
        stack.push(4);
        Test("Test2", stack, 3);
    
        stack.push(2);
        Test("Test3", stack, 2);
    
        stack.push(3);
        Test("Test4", stack, 2);
    
        stack.pop();
        Test("Test5", stack, 2);
    
        stack.pop();
        Test("Test6", stack, 3);
    
        stack.pop();
        Test("Test7", stack, 3);
    
        stack.push(0);
        Test("Test8", stack, 0);
    
        return 0;
    }
    

    运行结果

    Test1 begins: Passed.
    Test2 begins: Passed.
    Test3 begins: Passed.
    Test4 begins: Passed.
    Test5 begins: Passed.
    Test6 begins: Passed.
    Test7 begins: Passed.
    Test8 begins: Passed.
    

    参考

    《剑指offer》

    相关文章

      网友评论

        本文标题:剑指offer - 包含min函数的栈

        本文链接:https://www.haomeiwen.com/subject/jrusjqtx.html