首页 > 代码库 > LeetCode之Min Stack
LeetCode之Min Stack
1.原文问题描述：
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.
2.问题翻译
设计一个栈，使它能够同时支持 push, pop, top方法并且能够同时检索最小值push(x) -- 把元素X放到栈中pop() --将栈顶元素移除top() --获取栈顶元素getMin() --检索出栈中最小的值
3.解决思路
a:最简单直接的就是通过Java自己提供的栈，然后因为栈提供了出栈（pop()）进栈(push())还有栈顶元素(peek())的方法，我们需要做的就是宁外设置一个变量或者使用一个其他的栈来保持最小的元素，在进栈出栈的时候来更新这个值，从而就可以获取到了最小值了
b:不使用Java提供的内置栈的实现方式，这个需要我们来模仿栈的实现过程
4.实现方式（b）
节点的定义（Node.java）
package minStack;/** * 栈中的节点定义（保存节点元素的同时需要保存栈中最小的元素的值） * @author wudy * */class Node { int value;//当前元素的值 int minValue;//用来保存栈中最小的元素(只需要在站定元素中设置这个属性就行了) Node next;//指向下一节点，模仿栈的实现 /** * 构造函数，实例化栈的节点 * @param value */ public Node(int value) { this.value = http://www.mamicode.com/value;>最小值栈的实现（MinStack.java）
package minStack;class MinStack { Node top = null; /** * 入栈，在入栈的同时需要检查更新元素的最小值 * @param x */ public void push(int x) { if (top == null) { top = new Node(x); top.minValue = http://www.mamicode.com/x;>测试类（MinStackTest.java）
package minStack;public class MinStackTest { /** * @param args */ public static void main(String[] args) { MinStack minStack = new MinStack(); for(int index = 0;index < 10;index++){ minStack.push(index); } System.out.println("栈顶元素:"+minStack.top()); System.out.println("最小元素:"+minStack.getMin()); System.out.println("栈顶元素出栈"); minStack.pop(); System.out.println("栈顶元素:"+minStack.top()); System.out.println("最小元素:"+minStack.getMin()); }}5.主要考察了数据结构中栈的实现和定义，比较简单
LeetCode之Min Stack
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。