欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【leetcode】155. 最小栈( Min Stack )

程序员文章站 2024-01-19 19:20:04
...

题目描述

【leetcode】155. 最小栈( Min Stack )
设计一个支持 push,pop,top 操作,并能在常数时间内检索到最小元素的栈。

  • push(x) – 将元素 x 推入栈中。
  • pop() – 删除栈顶的元素。
  • top() – 获取栈顶元素。
  • getMin() – 检索栈中的最小元素。

【leetcode】155. 最小栈( Min Stack )

第一次解答

思路:
弄一个单链表,top永远指向单链表起始
添加元素在单链表头部添加
为了实现常量检索最小值,每个单链表元素额外附带一个元素min
min存储了该元素添加后,此时stack内的最小值

class cMyLink {
public:
    cMyLink *next;
    int val;
    int min_val;
    cMyLink(int x){
        next = nullptr;
        val = x;
    }
private:
    cMyLink(){ }
};

class MinStack {
public:

    cMyLink *p_top;
    /** initialize your data structure here. */
    MinStack() {
        p_top = nullptr;
    }
    
    void push(int x) {
        cMyLink *p_top_last = p_top;
        p_top = new cMyLink(x);
        p_top->next = p_top_last;
        
        if(nullptr == p_top_last || x < p_top_last->min_val){
            p_top->min_val = x;
        }
        else {
            p_top->min_val = p_top_last->min_val;
        }
    }
    
    void pop() {
        cMyLink *p_top_next = p_top->next;
        delete p_top;
        p_top = p_top_next;
    }
    
    int top() {
        return p_top->val;
    }
    
    int getMin() {
        return p_top->min_val;
    }
};

结果:
【leetcode】155. 最小栈( Min Stack )

第二次解答

思路:
优化思路1,每个单链表附带一个指针指向当前最小值

// 优化思路1,每个单链表附带一个指针指向当前最小值

class cMyLink {
public:
    cMyLink *next;
    int val;
    cMyLink *p_min_val;
    cMyLink(int x){
        next = nullptr;
        val = x;
    }
private:
    cMyLink(){ }
};

class MinStack {
public:

    cMyLink *p_top;
    /** initialize your data structure here. */
    MinStack() {
        p_top = nullptr;
    }
    
    void push(int x) {
        cMyLink *p_top_last = p_top;
        p_top = new cMyLink(x);
        p_top->next = p_top_last;
        
        // 记录最小值
        if(nullptr == p_top_last || x < p_top_last->p_min_val->val){
            p_top->p_min_val = p_top;
        }
        else {
            p_top->p_min_val = p_top_last->p_min_val;
        }
    }
    
    void pop() {
        cMyLink *p_top_next = p_top->next;
        delete p_top;
        p_top = p_top_next;
    }
    
    int top() {
        return p_top->val;
    }
    
    int getMin() {
        return p_top->p_min_val->val;
    }
};

结果:
【leetcode】155. 最小栈( Min Stack )

第三次解答

思路:
看了这里的题解,之前的解答相当于实现了同步的辅助stack
现在写一个不同步的辅助stack
另外,为了简洁,体现异步辅助栈思想,这里用现成的stack

#include <stack>
class MinStack {
public:
    stack<int> data;
    stack<int> helper;//辅助栈

    MinStack() {
    }
    
    void push(int x) {
        data.push(x);

        // 记录最小值,注意x == helper.top()时也要入栈
        if(helper.empty() || x <= helper.top()){
            helper.push(x);
        }
    }
    
    void pop() {
        if(data.top() == helper.top()){
            helper.pop();
        }
        data.pop();

    }
    
    int top() {
        return data.top();
    }
    
    int getMin() {
        return helper.top();
    }
};

结果:
【leetcode】155. 最小栈( Min Stack )

相关/参考链接

使用辅助栈(同步和不同步,Python 代码、Java 代码)