摘要:双栈法复杂度时间空间思路暴力的方法是遍历一遍栈得出最小值,这样不用任何空间。因为这个最小值的顺序也是先进后出,我们同样用一个栈来记录。这样主栈在时,如果该值小于等于副栈顶,就也进副栈中。当主栈时,如果出的元素是副栈栈顶的话,副栈也要。
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 { Stackstk = 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 设计一个支持 push,pop,top 操作,并能在常数时间内检索到最小元素的栈。 push(x) -- ...
摘要:题目地址题目描述设计一个支持,,操作,并能在常数时间内检索到最小元素的栈。将元素推入栈中。删除栈顶的元素。示例返回返回返回解答每次入栈都放入两个元素,分别是当前元素,和当前的最小元素因此放入之前需要和当前值进行比较。 题目地址:https://leetcode-cn.com/probl...题目描述:设计一个支持 push,pop,top 操作,并能在常数时间内检索到最小元素的栈。 p...
摘要:如果继续降序,说明又向左走了,这样等到下次向右走得时候也要再次更新最小值。这样,序列无效的条件就是违反了这个最小值的限定。我们同样可以用本题的方法解,不过是从数组的后面向前面遍历,因为在后面了。栈的增长方向也是从高向低了。 Verify Preorder Sequence in Binary Search Tree Given an array of numbers, verify ...
摘要:复杂度思路维护一个里面有最大值和最小值。如果当前值小于的最小值,那么就将原来的压进去栈,然后在用这个新的的值再进行更新。如果没有适合返回的值,就重新更新当前的。 Leetcode[132] Pattern Given a sequence of n integers a1, a2, ..., an, a 132 pattern is a subsequence ai, aj, ak ...
摘要:在线网站地址我的微信公众号完整题目列表从年月日起,每天更新一题,顺序从易到难,目前已更新个题。这是项目地址欢迎一起交流学习。 这篇文章记录我练习的 LeetCode 题目,语言 JavaScript。 在线网站:https://cattle.w3fun.com GitHub 地址:https://github.com/swpuLeo/ca...我的微信公众号: showImg(htt...
阅读 2842·2021-11-24 09:39
阅读 3069·2021-11-19 10:00
阅读 1493·2021-10-27 14:17
阅读 1776·2021-10-14 09:43
阅读 928·2021-09-03 10:30
阅读 3387·2019-08-30 15:54
阅读 2687·2019-08-30 13:05
阅读 1947·2019-08-30 11:02