LeetCode剑指offer 包含min函数的栈 Java

题目描述 包含min函数的栈 MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.min(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.min(); --> 返回 -2.

方法一： 数据栈 A ： 栈 A用于存储所有元素，保证入栈 push() 函数、出栈 pop() 函数、获取栈顶 top() 函数的正常逻辑。 辅助栈 B ： 栈 B中存储栈 A中所有 非严格降序 的元素，则栈 A中的最小元素始终对应栈 B 的栈顶元素，即 min() 函数只需返回栈 B 的栈顶元素即可。

push(x)：

将x压入栈A若B为空或者x<=B的栈顶元素，则将x压入B

pop() : 1.A出栈 记作y 2 如果y 等于B 的栈顶元素，则B出栈

top(): 返回A的栈顶元素 min():返回B的栈顶元素

class MinStack { Stack<Integer> A,B; /** initialize your data structure here. */ public MinStack() { A = new Stack<Integer>(); B = new Stack<Integer>(); } public void push(int x) { A.add(x); if(B.empty()||B.peek() >= x){ B.add(x); } } public void pop() { if(A.pop().equals(B.peek())){ B.pop(); } } public int top() { return A.peek(); } public int min() { return B.peek(); } }

方法二：引入链表 建一个ListNode结构类，里面有3个变量，val存指，min存当前元素到栈底的最小值，next指向下一个节点 MinStack类维护一个ListNode头节点，初始为null push（）：

当头节点为null时直接新建一个头节点，值为x，min也为x，next为null当头节点不为null时，在头节点之前插入一个节点，值为x，min取x与头节点存储的最小值比较之后的最小值，next指向头节点将新的节点重新赋值给头节点，也就是每次push都将值插入头节点之前 pop（）：直接将头节点指向头节点的下一个节点，也就是每次pop头节点，从而实现后进先出的栈操作 top（）：直接返回头节点的值即可 min（）：直接返回头节点的min值即可 class ListNode{ int val; int min; ListNode next; public ListNode(int val,int min,ListNode next){ this.val = val; this.min = min; this.next = next; } } class MinStack { ListNode head; /** initialize your data structure here. */ public MinStack() { } public void push(int x) { if(empty()){ head = new ListNode(x,x,null); }else{ head = new ListNode(x,Math.min(x,head.min),head); } } public boolean empty(){ return head == null; } public void pop() { head = head.next; } public int top() { return head.val; } public int min() { return head.min; } }