1, 题目

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

  1. push(x) —— 将元素 x 推入栈中。
  2. pop() —— 删除栈顶的元素。
  3. top() —— 获取栈顶元素。
  4. getMin() —— 检索栈中的最小元素。

示例:

  1. MinStack minStack = new MinStack();
  2. minStack.push(-2);
  3. minStack.push(0);
  4. minStack.push(-3);
  5. minStack.getMin();   --> 返回 -3.
  6. minStack.pop();
  7. minStack.top();      --> 返回 0.
  8. minStack.getMin();   --> 返回 -2.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/min-stack
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2, 算法

  1. class MinStack() {
  3.     /** initialize your data structure here. */
  4.     val buffer = scala.collection.mutable.ArrayBuffer[Int]()
  5.     var value = Int.MaxValue
  7.     def push(x: Int): Unit = {
  8.         value = value.min(x)
  9.         buffer.append(x)
  10.     }
  12.     def pop(): Unit = {
  13.         if (buffer.nonEmpty) {
  14.             buffer.remove(buffer.length - 1)
  15.             if (buffer.nonEmpty) {
  16.                 value = buffer.min
  17.             } else {
  18.                 value = Int.MaxValue
  19.             }
  21.         } else {
  22.             throw new NoSuchElementException()
  23.         }
  24.     }
  26.     def top(): Int = {
  27.         buffer.last
  28.     }
  30.     def getMin(): Int = {
  31.         if (buffer.nonEmpty) {
  32.             value
  33.         } else {
  34.             throw new NoSuchElementException()
  35.         }
  36.     }
  37. }
  1. class MinStack:
  2.     def __init__(self):
  3.         """
  4.         initialize your data structure here.
  5.         """
  6.         self.buffer = []
  7.         self.value = None
  9.     def push(self, x: int) -> None:
  10.         self.buffer.append(x)
  11.         if self.value is not None:
  12.             self.value = min(self.value, x)
  13.         else:
  14.             self.value = x
  16.     def pop(self) -> None:
  17.         if self.buffer:
  18.             x = self.buffer.pop()
  19.             if self.buffer:
  20.                 self.value = min(self.buffer)
  21.             else:
  22.                 self.value = None
  23.             return x
  25.     def top(self) -> int:
  26.         if self.buffer:
  27.             return self.buffer[-1]
  29.     def getMin(self) -> int:
  30.         if self.value is not None:
  31.             return self.value