腾讯三面: 设计一个支持xxx并能在常数时间内检索到最小元素的栈

力扣155：设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈

近日，有网友面试腾讯的时候遇到这道算法题，接下来我将详细讲述（Java）

网友留言

双栈解法

使用两个栈，一个栈存储实际数据，另外一个栈存储最小值，在常数时间内检索到最小元素，本质上是通过空间换时间的思想，直接看代码：

class MinStack { // 存储实际数据的栈 Deque xStack;// 存储最小值的栈 Deque minStack; public MinStack { xStack = new LinkedList; minStack = new LinkedList; minStack.push(Integer.MAX_VALUE); } public void push(int x) { xStack.push(x); minStack.push(Math.min(minStack.peek, x)); } public void pop { xStack.pop; minStack.pop; } public int top { return xStack.peek; } // 在常数时间内检索到最小值 public int getMin { return minStack.peek; }}参考：力扣官方题解

双栈解法的时间复杂度，对于每个操作都是 O(1) ，空间复杂度是 O(n)

最优解法

面试官继续追问有没有最优解，其实有办法不用两个栈保存双份数据，只用一个栈的解法如下，思路是在栈里面保存差值：

class MinStack { Deque stack; Long minVal; public MinStack { this.stack = new LinkedList<>; this.minVal = Long.MAX_VALUE; } public void push(int val) { if (this.stack.isEmpty) { this.stack.push(0l); this.minVal = (long)val; } else { long diff = (long)val - this.minVal; this.stack.push(diff); this.minVal = diff > 0 ? this.minVal : val; } } public void pop { long diff = this.stack.pop; if (diff < 0) { this.minVal = this.stack.isEmpty ? Long.MAX_VALUE : this.minVal - diff; } } public int top { return this.stack.peek < 0l ? Math.toIntExact(this.minVal) : Math.toIntExact(this.minVal + this.stack.peek); } public int getMin { return Math.toIntExact(this.minVal); }}

有个细节，因为存储的是差值，并且题目说明 Integer.MIN_VALUE <= val <= Integer_MAX_VALUE，所以 diff 要用 Long 声明，防止计算溢出