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.
Реализуйте стек,
поддерживающий операции push, pop, top и извлечение наименьшего элемента за
константное время.
·
push(x) – Положить
элемент x на верх стека.
·
pop() – Извлечь элемент с вершины стека.
·
top() – Вернуть верхний элемент.
·
getMin() – Вернуть минимальный элемент из стека.
// C++
class MinStack {
public:
/** initialize your data structure here. */
MinStack()
{
}
void push(int x) {
}
void pop() {
}
int top() {
}
int getMin() {
}
};
// Java
public class MinStack {
/** initialize your data structure here. */
public MinStack() {
}
public void push(int x) {
}
public void pop() {
}
public int top() {
}
public int getMin() {
}
}
структуры данных - стек
Заведем два стека. В стеке
s будем моделировать вставку и удаление обычным образом. В стеке mn будем
поддерживать минимум. При выполнении операции push(x):
·
Если стек пустой, то заносим x в стек mn.
·
Если стек непустой, то заносим min(x, mn.top()) в стек mn.
Тогда минимум в стеке
всегда находится на вершине стека mn.
Реализация алгоритма
class
MinStack
{
public:
stack<int>
s, mn;
void push(int x)
{
s.push(x);
if (mn.empty())
mn.push(x);
else
mn.push(min(x,mn.top()));
}
void pop()
{
s.pop();
mn.pop();
}
int top()
{
return
s.top();
}
int getMin()
{
return
mn.top();
}
};
Java реализация
public class MinStack
{
public Stack<Integer> s, mn;
public MinStack()
{
s = new Stack<Integer>();
mn = new Stack<Integer>();
}
public void push(int x)
{
s.push(x);
if (mn.empty())
mn.push(x);
else
mn.push(Math.min(x,mn.peek()));
}
public void pop()
{
s.pop();
mn.pop();
}
public int top()
{
return s.peek();
}
public int getMin()
{
return mn.peek();
}
}