剑指offer - 包含min函数的栈

题目

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素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》