（栈）155. 最小栈

题目设计一个支持 push pop top 操作并能在常数时间内检索到最小元素的栈。实现 MinStack 类:MinStack() 初始化堆栈对象。void push(int val) 将元素val推入堆栈。void pop() 删除堆栈顶部的元素。int top() 获取堆栈顶部的元素。int getMin() 获取堆栈中的最小元素。示例 1:输入[“MinStack”,“push”,“push”,“push”,“getMin”,“pop”,“top”,“getMin”][[],[-2],[0],[-3],[],[],[],[]]输出[null,null,null,null,-3,null,0,-2]解释MinStack minStack new MinStack();minStack.push(-2);minStack.push(0);minStack.push(-3);minStack.getMin(); -- 返回 -3.minStack.pop();minStack.top(); -- 返回 0.minStack.getMin(); -- 返回 -2.提示-231 val 231 - 1pop、top 和 getMin 操作总是在 非空栈 上调用push, pop, top, and getMin最多被调用 3 * 104 次# 思路思路首先理解题目意思有两个目的实现栈功能可以通过getMin获取到 栈 中的 最小值辅助栈在这里这个最小值的获取便使用栈去承载这个最小值使用minStack表示实际元素的存储的栈使用stack表示栈先进后出只要stack中有有元素出栈则对应的这个最小值minstack栈也要出栈其出栈后minstack栈内的第一个元素还是stack栈里面的最小值示例如下// 初始值 stacknull minStackINT_MAX // -2入栈 stack-2 minStackINT_MAX-2 // 0入栈 stack-20 minStackINT_MAX-2-2 // -3入栈 stack-20-3 minStackINT_MAX-2-2-3Deque中用于栈操作入栈、出栈、查看栈顶的核心方法说明入栈push(E e)将元素压入栈顶即添加到Deque的头部遵循 LIFO 原则出栈pop()移除并返回栈顶元素即Deque的头部元素遵循 LIFO 原则查看栈顶元素不移除peek()获取栈顶元素即Deque的头部元素但不移除该元素单向链表使用Node去存储这个过程每个节点对应栈里的一个元素同时携带了当前栈的最小值信息key存入栈的元素本身的值供top()方法返回栈顶元素value从栈底到当前节点为止栈内的最小值供getMin()方法直接返回next指向下一个节点栈中更靠下、更早入栈的元素整个栈用单链表的头部作为栈顶入栈 链表头插法新节点插在最前面出栈 链表头删法直接把头指针后移一位所有操作都是 O (1) 时间classNode{intkey;intvalue;Nodenext;publicNode(intkey,intvalue){this.keykey;this.valuevalue;this.nextnull;};publicNode(intkey,intvalue,Nodenode){this.keykey;this.valuevalue;// 反向this.nextnode;}}注意入栈时更新的是当前这整个链表即nodenewNode而非node.nextnewNode出栈时nodenode.next;// 初始值 innull nodenull // -2入栈 stack-2 node{-2,-2} // 0入栈 stack-20 node{0,-2}{-2,-2} // -3入栈 stack-20-3 node{-3,-3}{0,-2}{-2,-2} // getMin() // pop() stack-20 node{0,-2}{-2,-2}算法辅助栈classMinStack{DequeIntegerstack;DequeIntegerminStack;publicMinStack(){stacknewLinkedList();minStacknewLinkedList();minStack.push(Integer.MAX_VALUE);}publicvoidpush(intval){stack.push(val);minStack.push(Math.min(minStack.peek(),val));}publicvoidpop(){stack.pop();minStack.pop();}publicinttop(){returnstack.peek();}publicintgetMin(){returnminStack.peek();}}/** * Your MinStack object will be instantiated and called as such: * MinStack obj new MinStack(); * obj.push(val); * obj.pop(); * int param_3 obj.top(); * int param_4 obj.getMin(); */单向链表classMinStack{Nodenode;publicMinStack(){}publicvoidpush(intval){if(nodenull){nodenewNode(val,val);}else{intminMath.min(node.value,val);NodenewNodenewNode(val,min,node);nodenewNode;}}publicvoidpop(){nodenode.next;}publicinttop(){returnnode.key;}publicintgetMin(){returnnode.value;}classNode{intkey;intvalue;Nodenext;publicNode(intkey,intvalue){this.keykey;this.valuevalue;this.nextnull;};publicNode(intkey,intvalue,Nodenode){this.keykey;this.valuevalue;this.nextnode;}}}/** * Your MinStack object will be instantiated and called as such: * MinStack obj new MinStack(); * obj.push(val); * obj.pop(); * int param_3 obj.top(); * int param_4 obj.getMin(); */