LeetCodeDay24 —— 最小栈

155. 最小栈

描述

• 设计一个支持 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.

思路

1. 题目要求MinStack兼顾Stack和最小队列两种容器的特性，因此可以利用一个Stack加一个Vector来共同存储每个元素。利用空间换时间，保证常数时间的getMin操作。
2. Vector的插入需要移动元素，比较耗时，因此可以将其改为一个Stack，负责按顺序存储当前最小元素。
3. 值得注意的是，当栈顶元素出栈时，不会存在比栈顶元素大，比次栈顶元素小的元素还在栈内。如3,1,2依次入栈。当1出栈时，2已经早早就出栈了。

class MinStack_155_01 {
 public:
  MinStack() {}

  void push(int x) {
    s.push(x);
    auto iter = vec.begin();
    while (iter != vec.end()) {
      if (*iter > x) break;
      ++iter;
    }
    vec.insert(iter, x);
  }

  void pop() {
    int tmp = s.top();
    s.pop();
    auto iter = vec.begin();
    while (iter != vec.end()) {
      if (*iter == tmp) break;
      ++iter;
    }
    if (iter != vec.end()) vec.erase(iter);
  }

  int top() { return s.top(); }

  int getMin() { return vec.front(); }

 private:
  vector<int> vec;
  stack<int> s;
};

class MinStack_155_02 {
 private:
  stack<int> s, ms;

 public:
  MinStack() {}

  void push(int x) {
    if (ms.empty() || x <= ms.top()) ms.push(x); // 注意这里是<=
    s.push(x);
  }

  void pop() {
    int tmp = s.top();
    s.pop();
    if (tmp == ms.top()) ms.pop();
  }

  int top() { return s.top(); }

  int getMin() { return ms.top(); }
};