[Leetcode] Min Stack 最小栈

YorkChen 发布于2019-08-14 12:31 / 2049人阅读

摘要：双栈法复杂度时间空间思路暴力的方法是遍历一遍栈得出最小值，这样不用任何空间。因为这个最小值的顺序也是先进后出，我们同样用一个栈来记录。这样主栈在时，如果该值小于等于副栈顶，就也进副栈中。当主栈时，如果出的元素是副栈栈顶的话，副栈也要。

Min Stack

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.

双栈法 复杂度

时间 O(N) 空间 O(1)

思路

暴力的方法是遍历一遍栈得出最小值，这样不用任何空间。但如果我们能使用空间来记录到目前为之最小的数呢？我们只要记录一个最小数的顺序，和栈的操作顺序对应起来就可以在任何时候做到O(1)获取最小值了。因为这个最小值的顺序也是先进后出，我们同样用一个栈来记录。这样主栈在push时，如果该值小于等于副栈顶，就也push进副栈中。当主栈pop时，如果pop出的元素是副栈栈顶的话，副栈也要pop。

注意

判断是否加入副栈时，等于的情况也要加入，因为可能有多个重复的最小值，我们也需要多次抛出这些重复的最小值

当栈为空时，peek会抛出异常，这里要和面试官沟通好如何处理栈为空的情况

代码

class MinStack {
    
    Stack stk = new Stack();
    Stack min = new Stack();
    
    public void push(int x) {
        stk.push(x);
        if(min.isEmpty() || x <= min.peek()){
            min.push(x);
        }
    }

    public void pop() {
        int x = stk.pop();
        if(!min.isEmpty() && min.peek() == x){
            min.pop();
        }
    }

    public int top() {
        if(!stk.isEmpty()){
            return stk.peek();
        } else {
            return 0;
        }
    }

    public int getMin() {
        if(!min.isEmpty()){
           return min.peek();
        } else {
            return 0;
        }
    }
}

2018/2

class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.mins = []
        self.values = []
        

    def push(self, x):
        """
        :type x: int
        :rtype: void
        """
        self.values.append(x)
        if not self.mins or x <= self.mins[-1]:
            self.mins.append(x)
        

    def pop(self):
        """
        :rtype: void
        """
        result = self.values.pop() if self.values else None
        if result is not None and self.mins and result == self.mins[-1]:
            self.mins.pop()
        

    def top(self):
        """
        :rtype: int
        """
        return self.values[-1] if self.values else None

        

    def getMin(self):
        """
        :rtype: int
        """
        return self.mins[-1] if self.mins else None

后续 Follow Up

Q：如果还要加一个getMax()方法呢？
A：同样用一个栈，但是入栈的判断条件是大于等于栈顶。

云服务器 GPU云服务器 LeetCode Stack LeetCode_String leetcode_35_SearchIn

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64525.html

LeetCode 155：最小栈 Min Stack

摘要：删除栈顶的元素。可以另外新建一个栈来顺序存入数据最小值。另外在数据入栈时需要判断该值是否比辅助栈的栈顶元素的值更小，如果更小，也应该将它加入辅助栈。并且需要判断辅助栈是否为空，在不空的条件下才可以取栈顶元素比较，否则会溢出。 LeetCode 155：最小栈 Min Stack 设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。 push(x) -- ...

LeexMuller 2019-08-19 10:16 评论0 收藏0
力扣(LeetCode)155

摘要：题目地址题目描述设计一个支持，，操作，并能在常数时间内检索到最小元素的栈。将元素推入栈中。删除栈顶的元素。示例返回返回返回解答每次入栈都放入两个元素，分别是当前元素，和当前的最小元素因此放入之前需要和当前值进行比较。题目地址：https://leetcode-cn.com/probl...题目描述：设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。 p...

Scliang 2019-08-16 15:21 评论0 收藏0
[Leetcode] Verify Preorder Sequence in Binary Sear

摘要：如果继续降序，说明又向左走了，这样等到下次向右走得时候也要再次更新最小值。这样，序列无效的条件就是违反了这个最小值的限定。我们同样可以用本题的方法解，不过是从数组的后面向前面遍历，因为在后面了。栈的增长方向也是从高向低了。 Verify Preorder Sequence in Binary Search Tree Given an array of numbers, verify ...

未东兴 2019-08-14 12:46 评论0 收藏0
LeetCode[132] Pattern

摘要：复杂度思路维护一个里面有最大值和最小值。如果当前值小于的最小值，那么就将原来的压进去栈，然后在用这个新的的值再进行更新。如果没有适合返回的值，就重新更新当前的。 Leetcode[132] Pattern Given a sequence of n integers a1, a2, ..., an, a 132 pattern is a subsequence ai, aj, ak ...

go4it 2019-08-16 10:26 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0