155.最小栈

题目描述题解一(辅助栈/双栈法)(易于理解)思路代码在 Java 中推荐使用 Deque具体实现为 ArrayDeque来代替传统的 Stack 类因为它的性能更好classMinStack{// 数据栈存储实际的值privateDequeIntegerdataStack;// 辅助栈存储每次 push 时的当前最小值privateDequeIntegerminStack;////解析1:彻底理解minStack//publicMinStack(){dataStacknewArrayDeque();minStacknewArrayDeque();// 压入一个哨兵节点避免 push 时判空操作简化代码minStack.push(Integer.MAX_VALUE);}publicvoidpush(intval){dataStack.push(val);// 将当前值与目前的最小值比较将较小者压入最小栈minStack.push(Math.min(minStack.peek(),val));}publicvoidpop(){// 两个栈同步弹出dataStack.pop();minStack.pop();}publicinttop(){returndataStack.peek();}publicintgetMin(){returnminStack.peek();}}解析1:彻底理解minStack模拟2-1-5的push与pop操作复杂度分析时间复杂度O(1)O(1)O(1)。所有的操作push, pop, top, getMin都只需要对栈进行单次压入或弹出不涉及任何循环遍历空间复杂度O(n)O(n)O(n)。其中nnn为栈中元素的个数。我们需要一个额外的辅助栈 minStack在最坏情况下它的元素数量和 dataStack 一样多题解二(不使用辅助栈)(经典且巧妙的进阶面试题)思路代码classMinStack{// 存储差值的栈必须用 Long 防止 int 溢出privateDequeLongstack;// 维护当前的最小值privatelongmin;publicMinStack(){stacknewArrayDeque();}publicvoidpush(intval){if(stack.isEmpty()){// 如果是第一个元素差值存 0并记录 minstack.push(0L);////问题1:这里int类型的val不用先转为long类型吗?//minval;}else{// 计算差值压入值 - 当前最小值//在减法时产生的结果可能超出 int 的承受范围所以必须先将val转为long类型longdiff(long)val-min;stack.push(diff);// 如果差值小于 0说明遇到了更小的值更新 minif(diff0){minval;}}}publicvoidpop(){//可以省略,因为题目中明确说明了pop、top 和 getMin 操作总是在非空栈上调用//防御性编程if(stack.isEmpty())return;longdiffstack.pop();// 如果弹出的差值小于 0说明这个元素是当时的最小值// 弹出它之后我们需要恢复上一个最小值if(diff0){// 恢复公式旧 min 当前 min - diffminmin-diff;}}publicinttop(){longdiffstack.peek();// 如果差值小于 0说明当前的最小值就是栈顶元素的真实值if(diff0){return(int)min;}else{// 否则真实值 当前最小值 差值return(int)(mindiff);}}publicintgetMin(){return(int)min;}}问题1:这里int类型的val不用先转为long类型吗?复杂度分析时间复杂度O(1)O(1)O(1)。所有操作依然是纯粹的数学运算和单次栈操作空间复杂度O(n)O(n)O(n)。虽然我们仍然使用了一个栈来存储数据但相比于双栈法我们省略了辅助栈的O(n)O(n)O(n)空间开销。我们仅仅多用了一个 long 类型的变量 min达到了题目要求的极限