首页 > 代码库 > 【LeetCode 题解】Min Stack
【LeetCode 题解】Min Stack
同学推荐了LeetCode，相比其他的OJ，题量少，题目也比较经典，针对性特别强，适合练习。
LeetCode相关的网上资源比较多，不过，看到题目一定要自己做一遍，然后再去参考其他人的解法。
https://oj.leetcode.com/problems/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.
实现一个最小栈，时间复杂度为常量时间。
Stack(栈)是First in-Last out的数据结构。栈顶(top)指的是允许操作数据的一端，要与堆栈中高低地址不同的栈顶和栈底区别开来。
如果不考虑时间复杂度，实现题目的要求都比较简单，现在限定了不超过常量时间O（1），
就不能用简单的排序过滤实现了。
public class MinStack { //声明数据栈 private Stack<Integer> elementsStack=new Stack<Integer>(); //声明辅助栈 private Stack<Integer> supportStack=new Stack<Integer>(); /** * 考虑到时间复杂度的需求，添加一个辅助栈， * 每次入栈时将元素分别存入数据栈和辅助栈， * 辅助栈中的数据始终保持最小值在栈顶，需要获取最小值时，直接Peek()辅助栈即可。 */ public static void main(String[] args){ MinStack minStack=new MinStack(); minStack.push(0); minStack.push(1); minStack.push(0); System.out.print(minStack.getMin()); minStack.pop(); System.out.print(minStack.getMin()); } public void push(int x) { //始终保持辅助栈顶是最小元素 if(supportStack.empty() || x <= supportStack.peek()){ supportStack.push(x); } elementsStack.push(x); } public void pop() { //更新辅助栈 if(elementsStack.peek().equals(supportStack.peek())){ supportStack.pop(); } elementsStack.pop(); } public int top() { return elementsStack.peek(); } public int getMin() { //辅助栈 return supportStack.peek(); }}
【LeetCode 题解】Min Stack
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。