本文共 2376 字，大约阅读时间需要 7 分钟。
设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。
push(x) – 将元素 x 推入栈中。 pop() – 删除栈顶的元素。 top() – 获取栈顶元素。 getMin() – 检索栈中的最小元素。示例
MinStack minStack = new MinStack();
minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.getMin(); --> 返回 -2.
class MinStack(object): def __init__(self): """ initialize your data structure here. """ self.stack = [] # 存放所有元素 self.minStack = [] # 存放每一次压入数据时，栈中的最小值（如果压入数据的值大于栈中的最小值就不需要重复压入最小值，小于或者等于栈中最小值则需要压入） def push(self, x): """ :type x: int :rtype: void """ self.stack.append(x) if not self.minStack or self.minStack[-1]>=x: self.minStack.append(x) def pop(self): # 移除栈顶元素时，判断是否移除栈中最小值 """ :rtype: void """ if self.minStack[-1]==self.stack[-1]: del self.minStack[-1] self.stack.pop() def top(self): """ :rtype: int """ return self.stack[-1] def getMin(self): """ :rtype: int """ return self.minStack[-1]
以下是Java版本：
1.class MinStack { 2. // stack: store the stack numbers 3. private Stack stack = new Stack (); 4. // minStack: store the current min values 5. private Stack minStack = new Stack (); 6. 7. public void push(int x) { 8. // store current min value into minStack 9. if (minStack.isEmpty() || x <= minStack.peek()) 10. minStack.push(x); 11. stack.push(x); 12. } 13. 14. public void pop() { 15. // use equals to compare the value of two object, if equal, pop both of them 16. if (stack.peek().equals(minStack.peek())) 17. minStack.pop(); 18. stack.pop(); 19. } 20. 21. public int top() { 22. return stack.peek(); 23. } 24. 25. public int getMin() { 26. return minStack.peek(); 27. } 28.} 【分析】
这道题的关键之处就在于 minStack 的设计，push() pop() top() 这些操作Java内置的Stack都有，不必多说。
我最初想着再弄两个数组，分别记录每个元素的前一个比它大的和后一个比它小的，想复杂了。
第一次看上面的代码，还觉得它有问题，为啥只在 x<minStack.peek() 时压栈？如果，push(5), push(1), push(3) 这样minStack里不就只有5和1，这样pop()出1后， getMin() 不就得到5而不是3吗？其实这样想是错的，因为要想pop()出1之前，3就已经被pop()出了。.
minStack 记录的永远是当前所有元素中最小的，无论 minStack.peek() 在stack 中所处的位置。
转载地址：http://vsuvi.baihongyu.com/