设计一个支持push,pop,top等操作并且可以在O(1)时间内检索出最小元素的堆栈。
push(x)–将元素x插入栈中
pop()–移除栈顶元素
top()–得到栈顶元素
getMin()–得到栈中最小元素
样例
MinStack minStack = new MinStack();
minStack.push(-1);
minStack.push(3);
minStack.push(-4);
minStack.getMin(); --> Returns -4.
minStack.pop();
minStack.top(); --> Returns 3.
minStack.getMin(); --> Returns -1.
解题思路:用一个变量来维护当前栈的最小值,栈中的其他元素与当前栈的最小值有一定的联系。当然,这个最小值随着数据进出栈也是不断更新的。
下面用一组数据来说明:
假设有一个实际栈t1,一个虚拟栈t2,当前栈的最小值value,数据自左向右依次进栈,存放数据如下;
stack_t1: 9 7 5 3 1 10 8 6 4 2
stack_t2: 0 -2 -2 -2 -2 9 7 5 3 1
min_valu: 9 7 5 3 1 1 1 1 1 1
stack<int>tt;//这里建立虚拟栈,以下函数都是借助虚拟栈对实际栈操作 int min_v; MinStack() { } void push(int x) { if(tt.empty()){ min_v=x; tt.push(x-min_v); }else{ if(x<min_v){ tt.push(x-min_v); min_v=x; }else{ tt.push(x-min_v); } } } void pop() { if(tt.top()>=0){ tt.pop(); }else{ min_v=min_v-tt.top(); tt.pop(); } } int top() { return max(min_v,min_v+tt.top()); } int getMin() { return min_v; }
根据栈的特点,也可以建另一个栈来维护最小值,无非就是多开点空间。