155.最小栈

题目描述

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

题解：

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class MinStack {
public:
    MinStack() = default;

    void push(int val) {
        stack_.emplace(val, std::min(val, getMin()));
    }

    void pop() {
        stack_.pop();
    }

    void top() {
        return stack_.top().first;
    }

    int getMin() {
        if (stack_.empty()) return INT_MAX;
        return stack_.top().second;
    }
private:
    std::stack<std::pair<int, int>> stack_;
};