栈和队列

leetcode155. 最小栈

2021-05-19 390 1

简介 leetcode155. 最小栈,力扣链接地址:https://leetcode-cn.com/problems/min-stack/

1. 最小栈解题思路

1.1 原生的栈

C++/Java/Python 支持的栈(原生栈),可以实现 push、pop、top(peek), 但是要获取最小元素, 一种方法是通过暴力搜索,从头到尾遍历整个,那么时间复杂度是 O(n),不是在常数级获取最小值, 不符合题目的要求。


我们可以设置两个栈,一个数据栈 datastack,用于存放需要存放的数据,一个记录最小值的栈 sortedstack。

            upfile


每次 push 操作之后, 保存当前 push 元素之后数据栈中的最小值, 因为从第一次 push 到之后的每次 push 操作,我们知道每次 push 的值,也很容易知道当前的栈中的最小值。










1.2 绘解过程

给定一组数据,依次 push 到数据栈 datastack 中,每次 push 操作之后,也将最小值 push 到 sortedstack 中

                upfile


最终所有的数据 push 到 datastack 之后

                upfile


    数据栈 datastack 出栈的时候, 同时也将 sortedstack 出栈, 那么 sortedstack 栈顶就是当前数据栈 datastack 的最小值, 常数级获取最小值。----空间换取时间


1.3 优化

    我们发现, sortedstack 存在重复值, 那么可以在每次数据栈入栈时, 如果 当前元素 <= sortedstack 的栈顶, 那么也将元素压入 sortedstack


    数据栈出栈时, 当前出栈的元素 = sortedstack 的栈顶, 那么两个栈都出栈。


    比如:

    要入栈的4 <= sortedstack 的栈顶 7, 那么将4压入 sortedstack


            upfile




4 <= 4,也将4压入 sortedstack

            upfile



整个过程的逻辑,动图如下:


upfile



如果动图太快,可以点击视频观看,可以暂停:



// C++

class MinStack {

public:

    /** initialize your data structure here. */

    stack<int> dataStack;      // 数据栈

    stack<int> sortedStack;    // 有序栈(栈底最大,栈顶最小,有 <= 栈顶的元素才进行push)

 

    MinStack() {

 

    }

    void push(int val) {

        dataStack.push(val);

        // --有序栈

        // ----如果为空 则 push

        // ----如果val 不大于 当前栈顶 则 push

        if(sortedStack.empty() || val <= sortedStack.top())

            sortedStack.push(val);

    }

     

    void pop() {

        // 数据栈的栈顶如果与 有序栈的栈顶相等, 那么都出栈

        if(dataStack.top() == sortedStack.top())

            sortedStack.pop();

        dataStack.pop();

    }

     

    int top() {

        return dataStack.top();

    }

     

    int getMin() {

        return sortedStack.top();

    }

};


// Java

class MinStack {

    /** initialize your data structure here. */

    Stack<Integer> dataStack = new Stack<Integer> ();

    Stack<Integer> sortedStack = new Stack<Integer> ();

    public MinStack() {

    }

    public void push(int val) {

        dataStack.push(val);

        // --有序栈

        // ----如果为空 则 push

        // ----如果val 不大于 当前栈顶 则 push

        if(sortedStack.empty() || val <= sortedStack.peek())

            sortedStack.push(val);

        System.out.println(sortedStack);

    }  

    public void pop() {

        // 数据栈的栈顶如果与 有序栈的栈顶相等, 那么都出栈

        // 注意 Stack中存储的是 Integer 对象 这里不能用 == 

        if(dataStack.peek().equals(sortedStack.peek()))

            sortedStack.pop();

        dataStack.pop();

    }  

    public int top() {

        return dataStack.peek();

    }

    public int getMin() {

        return sortedStack.peek();

    }

}


# Python

class MinStack:

    def __init__(self):

        """

        initialize your data structure here.

        """

        self.datastack = []    # 数据栈

        self.sortedstack = []  # 有序栈(栈底最大,栈顶最小,有 <= 栈顶的元素才进行push)


    def push(self, val: int-None:

        self.datastack.append(val)

        # --有序栈

        # ----如果为空 则 push

        # ----如果val 不大于 当前栈顶 则 push


        if not self.sortedstack or self.sortedstack[-1] >= val:

            self.sortedstack.append(val) 

    def pop(self-None:

        # 数据栈的栈顶如果与 有序栈的栈顶相等, 那么都出栈

        if self.datastack[-1== self.sortedstack[-1]:

            self.sortedstack.pop()

        self.datastack.pop()

    def top(self-int:

        return self.datastack[-1]

    def getMin(self-int:

        return self.sortedstack[-1]




点赞 1

文章评论

欢迎您:

纸上得来终觉浅,绝知此事要躬行!

112 文章 57741 浏览 3 评论

联系我

  •   QQ:    361352119
  •  Email:  lisimmy@sina.com
  • 微信: