首页 > 代码库 > LeetCode——Min Stack
LeetCode——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.
原题链接:https://oj.leetcode.com/problems/min-stack/
取出栈中的最小元素需要常数时间。
可以用两个栈来实现,其中一个栈存储的是全部的元素,而另一个栈存储的是前一个栈中的最小元素,这样每次更新后一个栈即可。
public class MinStack { private List<Integer> stack = new ArrayList<Integer>(); private List<Integer> minstack = new ArrayList<Integer>(); public void push(int x) { stack.add(x); if(minstack.isEmpty() || minstack.get(minstack.size()-1) >= x) minstack.add(x); } public void pop() { if(stack.isEmpty()) return; int tmp = stack.remove(stack.size()-1); if(!minstack.isEmpty() && tmp == minstack.get(minstack.size()-1)) minstack.remove(minstack.size()-1); } public int top() { if(!stack.isEmpty()) return stack.get(stack.size()-1); return -1; } public int getMin() { if(!minstack.isEmpty()) return minstack.get(minstack.size()-1); return -1; } }
LeetCode——Min Stack
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。