资讯专栏INFORMATION COLUMN

[Leetcode] Min Stack 最小栈

YorkChen / 1993人阅读

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

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:同样用一个栈,但是入栈的判断条件是大于等于栈顶。

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

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

相关文章

  • LeetCode 155:最小 Min Stack

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

    LeexMuller 评论0 收藏0
  • 力扣(LeetCode)155

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

    Scliang 评论0 收藏0
  • [Leetcode] Verify Preorder Sequence in Binary Sear

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

    未东兴 评论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 评论0 收藏0
  • 前端 | 每天一个 LeetCode

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

    张汉庆 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<