题目描述
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.
解题思路
此题目要求我们设计一个 最小栈, 除了支持 push , pop , top 这种 栈 的常规操作之外，还需要支持查找栈内最小元素。
这里我们使用了两个栈 ，list 和 minList ，前者用来存储数据，后者用来存储最小元素值（minList 的栈顶元素始终为当前 list 栈内的最小元素）。
- 在
push操作的时候，将当前元素压入list中，将当前元素和栈内最小元素之中的较小值压入minList中； - 在
pop操作的时候，两个栈同时执行出栈操作。 - 在
top操作的时候，取list的栈顶元素。 - 在
getMin操作的时候，取minList的栈顶元素。
参考代码
class MinStack {
public:
/** initialize your data structure here. */
stack<int> list, minList;
int minNum;
const int max = 2147483647;// “绝对”的最大值
MinStack()
{
minNum = max;
}
void push(int x)
{
if (list.size() > 0)
{
list.push(x);
if (x <= minNum)
{
minNum = x;
}
minList.push(minNum);
}
else
{
list.push(x);
minNum = x;
minList.push(minNum);
}
}
void pop()
{
if (list.size() > 0)
{
list.pop();
minList.pop();
minNum = getMin();
}
else
{
list.pop();
minList.pop();
minNum = max;
}
}
int top()
{
return list.top();
}
int getMin()
{
if (minList.size() > 0)
{
return minList.top();
}
else
{
return max;
}
}
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/
本文由 机灵鹤 SmartCrane 创作
本站文章所有原创文章, 转载前请务必署名
最后编辑时间为: 2018-09-27 20:20