【小白爬Leetcode155】2.3 最小栈 Min Stack

Leetcode 232 $\color{#228B22}{esay}$esay

点击进入原题链接：Leetcode155 最小栈 Min Stack

题目

Description

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

· push(x) – Push element x onto stack.
· pop() – Removes the element on top of the stack.
· top() – Get the top element.
· getMin() – Retrieve the minimum element in the stack.

Constraints:
Methods pop, top and getMin operations will always be called on non-empty stacks.

中文描述

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
· —— 将元素 x 推入栈中。
· —— 删除栈顶的元素。
· —— 获取栈顶元素。
· —— 检索栈中的最小元素。

思路一 额外用一个stack来记录每一个状态下栈的最小值

借用B站林沐****里的图，点击可进入该视频

从上图我们可以清晰地看到，如果我们只是用一个int min来记录栈中的最小值，那么当该最小值被弹出后，MIN=？ 就会不知所措，因此我们需要用一个额外的stack<int> _min来记录每一次push后栈中的最小值，具体实现如下：

设正常存储数据的栈为std::stack<int> _data;存储每一步最小值的
栈为std::stack<int> _min;，可以看到，当push的值x小于_min.top()的时候，或者_min还是个空栈的时候，说明最小值有更新，那么_min.push(x)。当当push的值x大于等于_min.top()的时候，说明最小值没有更新，直接_min.push(_min.top())即可。
当我们需要pop元素的时候，_min和_data一起pop即可实现最小值的同步更新。

完整代码如下：

class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {}
    
    void push(int x) {
        _data.push(x);
        if(_min.empty()||x<_min.top()) _min.push(x);
        else _min.push(_min.top());
    }
    
    void pop() {
        _data.pop();
        _min.pop();
    }
    
    int top() {
        return _data.top();
    }
    
    int getMin() {
        return _min.top();
    }
private:
    std::stack<int> _data;
    std::stack<int> _min;
};

思路二 每次push两个值

其实和思路一是一个道理，只是把两个栈合并成一个栈了：
每次push(x)的时候，先pushx本身，再pushx和栈顶元素的最小值。
这样，top()功能就return 栈的倒数第二个值，getMin()就返回栈的最后一个值，pop()的时候需要弹出两个元素。
完整代码如下：

class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {}
    
    void push(int x) {
        if(_data.empty()){
            _data.push(x);
            _data.push(x);
        }
        else{
            int temp = _data.top();
            _data.push(x);
            if(x<temp){
                _data.push(x);
            }else{
                _data.push(temp);
            }
        }

    }
    
    void pop() {
        _data.pop();
        _data.pop();
    }
    
    int top() {
        int temp = _data.top();
        _data.pop();
        int res = _data.top();
        _data.push(temp);
        return res;
    }
    
    int getMin() {
        return _data.top();
    }
private:
    std::stack<int> _data;
};

思路三 用链表来实现栈

评论区有个老哥说：

就想着要不自己动手用链表写一个栈吧。

参考：

class MinStack {
private:
 struct Node{
     int val;  // 当前节点的值
     int min;  // 当前以此节点为栈顶的栈内最小元素的值
     Node* next;  // 下一个节点，对应栈内的上一个元素

     Node(int x,int y):val(x),min(y),next(nullptr){}
 };
 Node* head = nullptr;

public:
 /** initialize your data structure here. */
 MinStack() {}
 
 void push(int x) {
     // 若栈空，则申请新节点空间并赋予头节点（相当于当前节点入栈）
     if(!head){
         head = new Node(x,x);
     }
     // 若栈非空，则更新新节点的栈内元素最小值后，将新节点插入栈顶，最后更新头节点
     else{
         Node* cur = new Node(x, x<head->min?x:head->min);
         cur->next = head; 
         head = cur;
     }
 }

 void pop() {
     // 让头节点指向自身的下一个节点即可
     // 不用管出栈之后的最小值变化，即使当前出栈元素就是最小值也无妨，
     // 因为每个节点的 min 值记录的都是栈底到此节点的元素最小值
     head = head->next;
 }

 int top() {
     // 直接返回头节点 val 值即可，头节点永远指向栈顶
     return head->val;
 }

 int getMin() {
     // 直接返回头节点 min 值即可，头节点的 min 值永远是栈内所有元素的最小值
     return head->min;
 }
 ~MinStack(){  //析构函数，释放栈
     while(head){
         Node* next = head->next;
         delete head;
         head = next;
     }
 }
};