【LeetCode & 剑指offer刷题】栈与队列题3：30 包含min函数的栈（155. Min Stack）
【LeetCode & 剑指offer 刷题笔记】目录（持续更新中...）
155. Min Stack
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
- push(x) -- Push element x onto stack.
- pop() -- Removes the element on top of the stack.
- top() -- Get the top element.
- getMin() -- Retrieve the minimum element in the stack.
Example:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> Returns -3.
minStack.pop();
minStack.top(); --> Returns 0.
minStack.getMin(); --> Returns -2.
//实现一个最小栈(要求获取最小值用常数时间)
//方法一：用两个栈，一个栈存数据，一个栈存各阶段最小数
class MinStack
{
private :
stack < int > s1 ; //存数据
stack < int > s2 ; //存各阶段最小数
public :
MinStack ()
{
}
void push ( int x )
{
s1 . push ( x );
if ( s2 . empty () || x <= s2.top ()) s2 . push ( x ); //如果s2为空，或者存入数小于等于之前最小数，则传入s2
}
void pop ()
{
if ( s1 . top () == s2 . top ()) s2 . pop (); //如果pop的是当前极小值，则s2也跟着pop
s1 . pop ();
}
int top ()
{
return s1 . top ();
}
int getMin ()
{
return s2 . top (); //栈顶元素为当前最小数
}
};
比较min栈与max队列
（1） if ( s2 . empty () || x <= s2 . top () ) s2 . push ( x ); //如果s2为空，或者存入数小于等于之前最小数，则传入s2
（2）
while (! index . empty () && num [ i ] >= num [ index . back () ] )
index . pop_back () ; //从队尾依次弹出队列中比当前num值小的元素，同时也能保证队列首元素为当前窗口最大值下标
index . push_back ( i ); //插入当前索引值，因为可能为其他窗口下的最大值