题目描述

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。 实现 MinStack 类: MinStack() 初始化 void push(int val) 将元素推入堆栈 void pop() 删除堆栈顶部的元素 int pop() 获取堆栈顶部的元素 int getMin() 获取堆栈中的最小元素

题解：

这道题首先要满足堆栈的特性 LIFO，其次是能够在常数时间内获取当前栈中最小的元素，因此我们可以用堆栈保存 个二元组，二元组的第一个元素是存入栈中的值，第二个元素是当前元素作为栈顶元素的时候，栈中的最小值。有 了这个思路，代码实现起来就很简单了。

 1class MinStack {
 2public:
 3    MinStack() = default;
 4
 5    void push(int val) {
 6        stack_.emplace(val, std::min(val, getMin()));
 7    }
 8
 9    void pop() {
10        stack_.pop();
11    }
12
13    void top() {
14        return stack_.top().first;
15    }
16
17    int getMin() {
18        if (stack_.empty()) return INT_MAX;
19        return stack_.top().second;
20    }
21private:
22    std::stack<std::pair<int, int>> stack_;
23};