Min Stack
本题收获：
1.可以利用两个栈操作。
2.栈的基本操作。
题目：
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.
思路：
我的思路：没有思路。
leetcode/dicuss思路：
弄2个stack，一个realStack，存放真正的数据；另外一个是minStack。
对于minStack元素中的每一个元素的意义是：push到 该位置的时候，当前最小元素的值。每次push进新元素的时候，更新minStack的值；每次pop的时候，由于minStack的定义，所以只需把 minStack和realStack一起进行一次pop操作就好了。
minstack只存储最小元素，每次Push时将输入元素与minstack中的元素对比，如果小于minstack则push，否则不操作。pop时，如果minstack的元素等于realstack中元素则pop，否则不操作。
代码：
class MinStack {
private:
stack<int> s1;
stack<int> s2;
public:
void push(int x) {
s1.push(x);
if (s2.empty() || x <= getMin()) s2.push(x);
}
void pop() {
if (s1.top() == getMin()) s2.pop();
s1.pop();
}
int top() {
return s1.top();
}
int getMin() {
return s2.top();
}
};我的带mian函数的测试代码：
// minStack.cpp : 定义控制台应用程序的入口点。
// #include "stdafx.h"
#include "iostream"
#include "stack"
using namespace std; class MyClass
{
public:
void push(int val);
void pop();
int minStack();
int top();
private:
stack<int> realstack;
stack<int> minstack;
}; void MyClass::push(int val)
{
realstack.push(val);
if (minstack.empty() || val <= minstack.top()) minstack.push(val);
} void MyClass::pop()
{
if (realstack.top() == minstack.top()) //注意pop的顺序，先比较在pop,不是先pop在比较
{
minstack.pop();
}
realstack.pop();
} int MyClass::top()
{
return realstack.top();
} int MyClass::minStack()
{
return minstack.top();
} int _tmain(int argc, _TCHAR* argv[])
{
MyClass solution;
int val = ;
cout << "the value is : ";
for (int i = ; i < ; i++)
{
cin >> val;
solution.push(val);
}
cout << "the min is : " << solution.minStack() << endl;
for (int i = ; i < ; i++)
{
int value = solution.top();
cout << "pop value is : " << value << endl;
//cin >> val;
solution.pop();
}
cout << "current min is : " << solution.minStack() << endl;
system("pause");
return ;
}
测试结果：
参考了：http://www.cnblogs.com/lihaozy/archive/2012/12/09/2809840.html
写的非常详细！
代码2：
class MinStack {
public:
vector<int> a;
vector<int> min;
MinStack() {
min.push_back();
}
void push(int x) {
a.push_back(x);
if (x < min.back()) {
min.push_back(x);
} else {
min.push_back(min.back());
}
}
void pop() {
a.pop_back();
min.pop_back();
}
int top() {
return a.back();
}
int getMin() {
return min.back();
}
};