LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 用一个辅助栈来保存栈中最小值

3 4 1 2

入栈过程
      3    3    1    1  // 最小值
| |  | |  | |  | |  |2|
| |  | |  | |  |1|  |1|
| |  | |  |4|  |4|  |4|
| |  |3|  |3|  |3|  |3|

可见，只有入栈值不大于上一个最小值时，才需要保存
因此，入栈时，辅助栈的同步状态如下

| |  | |  | |  | |  | |
| |  | |  | |  | |  | |
| |  | |  | |  |1|  |1|
| |  |3|  |3|  |3|  |3|

出栈过程
 1    1    3    3
|2|  | |  | |  | |  | |
|1|  |1|  | |  | |  | |
|4|  |4|  |4|  | |  | |
|3|  |3|  |3|  |3|  | |

可见，只有出栈值为最小值时，才需要删除该最小值
因此，出栈时，辅助栈的同步状态如下
| |  | |  | |  | |  | |
| |  | |  | |  | |  | |
|1|  |1|  | |  | |  | |
|3|  |3|  |3|  |3|  | |

• 实现如下

class MinStack {
 public:
  /** initialize your data structure here. */
  MinStack() {}

  void push(int x) {
    stackAll.emplace(x);
    if (empty(stackMin) || x <= stackMin.top()) {
      stackMin.emplace(x);
    }
  }

  void pop() {
    if (stackAll.top() == stackMin.top()) {
      stackMin.pop();
    }
    stackAll.pop();
  }

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

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

 private:
  stack<int> stackAll;
  stack<int> stackMin;
};