最小栈

法1

#include<iostream>
#include<stack>
#include<algorithm>
using namespace std;
class MinStack 
{
    stack<pair<int, int>> st;
public:
    MinStack() 
    {
    }

    void push(int val) 
    {
        if (st.size() == 0)
        {
            st.push({val,val});
        }
        else
        {
            //每一个压入栈的元素都会与栈顶元素进行比较，取较小值
            st.push({ val,min(val,st.top().second) });
        }
    }
    void pop() 
    {
        //头删
        st.pop();
    }

    int top() 
    {
        return st.top().first;
    }

    int getMin() 
    {
        return st.top().second;
    }
};
void test()
{
    MinStack* minStack = new MinStack();
    minStack->push(-2);
    minStack->push(0);
    minStack->push(-3);
    cout << minStack->getMin() << endl;   //--> 返回 -3
    minStack->pop();
    cout << minStack->top() << endl;    //--> 返回 0.
    cout << minStack->getMin() << endl;  //--> 返回 -2.
}
int main()
{
    test();
    system("pause");
    return 0;
}

法2：辅助栈

#include<iostream>
#include<stack>
#include<algorithm>
using namespace std;
//辅助栈写法：
struct ListNode 
{
    ListNode* next;
    int data;
};
class MinStack 
{
  //头指针
    ListNode* head;
    //辅助栈
    stack<int> helper;
public:
    MinStack() 
    {
        head = NULL;
    }

    void push(int val) 
    {
         //比较插入的值val和辅助栈栈顶的大小
        //如果当辅助栈为空的时候，表示是第一次向栈中插入元素
        if (helper.empty() || val < helper.top())
        {
            helper.push(val);
        }
        //头插法
        if (head == NULL)
        {
            ListNode* newNode = new ListNode;
            newNode->next = NULL;
            newNode->data = val;
            head = newNode;
        }
        ListNode* newNode = new ListNode;
        newNode->next = NULL;
        newNode->data = val;
        newNode->next = head;
        head = newNode;
    }
    void pop() 
    {
       //头删的时候判断，是否删除的是当前栈中最小元素
        if (head->data == helper.top())
        {
            helper.pop();
        }
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }

    int top() 
    {
        return head->data;
    }

    int getMin() 
    {
        return helper.top();
    }
};
void test()
{
    MinStack* minStack = new MinStack();
    minStack->push(-2);
    minStack->push(0);
    minStack->push(-3);
    cout << minStack->getMin() << endl;   //--> 返回 -3
    minStack->pop();
    cout << minStack->top() << endl;    //--> 返回 0.
    cout << minStack->getMin() << endl;  //--> 返回 -2.
}
int main()
{
    test();
    system("pause");
    return 0;
}