【算法速刷(4/100)】LeetCode —— 155.最小栈
每天写几题，健康每一天
最小栈问题，有许多种办法进行解答，首先需要锁定的条件是要求在实现栈功能之外，要在常数时间内检索最小元素。
一般这种O(1)查找最值都可以用一下方法
- 哈希表：使用哈希表存储对应栈大小时的栈最小值，在插入删除时都对哈希表进行一个同步操作
- 小根堆：使用小根堆维护所有数据，每次插入删除时都对堆内对应元素进行一个同步操作
- 最小栈：使用栈维护对应栈层的最小元素值，插入删除时对栈进行同步操作
以上操作都要求有O(n)的额外空间来记录栈对应层的最小值状态
在这里说一下最小栈的方式
class MinStack {
public:MinStack() {}void push(int val) {if(_minStk.empty() || val <= _minStk.top())_minStk.push(val);_stk.push(val);}void pop() {if(!_minStk.empty() && _stk.top() == _minStk.top())_minStk.pop();_stk.pop();}int top() {return _stk.top();}int getMin() {return _minStk.top();}
private:stack<int> _stk, _minStk;
};维护一个最小栈，该栈仅在栈为空，或者新入栈元素不大于最小栈的栈顶元素时才会入栈
同理，该栈仅在栈不为空，且出栈元素等于最小栈的栈顶元素时才会出栈
这样可以避免最小栈始终记录每一层的最小元素，即使新增元素后最小值还是不变，可以节省一定的存储空间