设计一个堆栈，使 getMinim()应该是 O (1)

小开

添加一个字段来保存最小值，并在 Pop ()和 Push ()期间更新它。这样，getMinim()将是 O (1) ，但 Pop ()和 Push ()将需要做更多的工作。

If minimum value is popped, Pop() will be O(n), otherwise they will still both be O(1). When resizing Push() becomes O(n) as per the Stack implementation.

这里有一个快速实现

public sealed class MinStack {
private int MinimumValue;
private readonly Stack<int> Stack = new Stack<int>();


public int GetMinimum() {
if (IsEmpty) {
throw new InvalidOperationException("Stack is empty");
}
return MinimumValue;
}


public int Pop() {
var value = Stack.Pop();
if (value == MinimumValue) {
MinimumValue = Stack.Min();
}
return value;
}


public void Push(int value) {
if (IsEmpty || value < MinimumValue) {
MinimumValue = value;
}
Stack.Push(value);
}


private bool IsEmpty { get { return Stack.Count() == 0; } }
}

小开

最佳答案

编辑: 这失去了“常量空间”的约束-它基本上是所需空间的两倍。我非常怀疑没有能够做到这一点，而不破坏运行时的复杂性(例如，使用 push/pop O (n))。注意，这并不会改变所需空间的 复杂性，例如，如果堆栈需要 O (n)空间，那么它仍然是 O (n) ，只是带有一个不同的常数因子。

非常数空间解

保持一个“重复”堆栈的“最低的所有值在堆栈中较低”。当您弹出主堆栈时，也弹出 min 堆栈。当您推送主堆栈时，推送新元素或当前最小值，以较低者为准。然后将 getMinimum()实现为 minStack.peek()。

所以用你的例子，我们会得到:

Real stack        Min stack


5  --> TOP        1
1                 1
4                 2
6                 2
2                 2

吸两次之后，你会得到:

Real stack        Min stack


4                 2
6                 2
2                 2

Please let me know if this isn't enough information. It's simple when you grok it, but it might take a bit of head-scratching at first :)

(当然，不利的一面是，它使空间需求增加了一倍。但是执行时间并没有明显减少——也就是说，它的复杂性还是一样的。)

编辑: 有一个变化，稍微更精细，但有更好的空间一般。我们仍然使用 min 堆栈，但是只有当我们从主堆栈弹出的值等于 min 堆栈上的值时才会从它中弹出。当推送到主堆栈的值小于当前最小值的 或平等时，我们只将用力推送到最小堆栈。这允许重复的最小值。getMinimum()仍然只是一个小操作。例如，取最初的版本，再按1，我们会得到:

Real stack        Min stack


1  --> TOP        1
5                 1
1                 2
4
6
2

从上面的两个堆栈中弹出，因为1 = = 1，留下:

Real stack        Min stack


5  --> TOP        1
1                 2
4
6
2

再次从主堆栈中弹出只有，因为5 > 1:

Real stack        Min stack


1                 1
4                 2
6
2

再次弹出两个堆栈，因为1 = = 1:

Real stack        Min stack


4                 2
6
2

最终得到的空间复杂度与最坏情况相同(是原始堆栈的两倍) ，但是如果我们很少得到“新的最小值或相等值”，那么空间使用情况会好得多。

编辑: 这是皮特邪恶计划的一个实现。我还没有彻底测试它，但我 好好想想它是好的:)

using System.Collections.Generic;


public class FastMinStack<T>
{
private readonly Stack<T> stack = new Stack<T>();
// Could pass this in to the constructor
private readonly IComparer<T> comparer = Comparer<T>.Default;


private T currentMin;


public T Minimum
{
get { return currentMin; }
}


public void Push(T element)
{
if (stack.Count == 0 ||
comparer.Compare(element, currentMin) <= 0)
{
stack.Push(currentMin);
stack.Push(element);
currentMin = element;
}
else
{
stack.Push(element);
}
}


public T Pop()
{
T ret = stack.Pop();
if (comparer.Compare(ret, currentMin) == 0)
{
currentMin = stack.Pop();
}
return ret;
}
}

小开

那么，push和 pop的运行时约束是什么？如果不要求它们是常数，那么只需计算这两个操作中的最小值(使它们成为哦(N))。否则，我不知道如何在不断增加空间的情况下做到这一点。

小开

这是我的实现版本。

struct MyStack {
int element;
int *CurrentMiniAddress;
};


void Push(int value)
{
// Create you structure and populate the value
MyStack S = new MyStack();
S->element = value;


if(Stack.Empty())
{
// Since the stack is empty, point CurrentMiniAddress to itself
S->CurrentMiniAddress = S;


}
else
{
// Stack is not empty


// Retrieve the top element. No Pop()
MyStack *TopElement = Stack.Top();


// Remember Always the TOP element points to the
// minimum element in ths whole stack
if (S->element CurrentMiniAddress->element)
{
// If the current value is the minimum in the whole stack
// then S points to itself
S->CurrentMiniAddress = S;
}
else
{
// So this is not the minimum in the whole stack
// No worries, TOP is holding the minimum element
S->CurrentMiniAddress = TopElement->CurrentMiniAddress;
}


}
Stack.Add(S);
}


void Pop()
{
if(!Stack.Empty())
{
Stack.Pop();
}
}


int GetMinimum(Stack &stack)
{
if(!stack.Empty())
{
MyStack *Top  = stack.top();
// Top always points to the minimumx
return  Top->CurrentMiniAddress->element;
}
}

小开

public class StackWithMin {
int min;
int size;
int[] data = new int[1024];


public void push ( int val ) {
if ( size == 0 ) {
data[size] = val;
min = val;
} else if ( val < min) {
data[size] = 2 * val - min;
min = val;


assert (data[size] < min);
} else {
data[size] = val;
}


++size;


// check size and grow array
}


public int getMin () {
return min;
}


public int pop () {
--size;


int val = data[size];


if ( ( size > 0 ) && ( val < min ) ) {
int prevMin = min;
min += min - val;
return prevMin;
} else {
return val;
}
}


public boolean isEmpty () {
return size == 0;
}


public static void main (String...args) {
StackWithMin stack = new StackWithMin();


for ( String arg: args )
stack.push( Integer.parseInt( arg ) );


while ( ! stack.isEmpty() ) {
int min = stack.getMin();
int val = stack.pop();


System.out.println( val + " " + min );
}


System.out.println();
}


}

它显式地存储当前的最小值，如果最小值改变了，而不是推动值，它推动一个值相同的差异在新的最小值的另一边(如果 min = 7，你推动5，它推动3而不是(5-| 7-5 | = 3) ，并设置 min 为5; 如果你然后弹出3当 min 是5它看到弹出的值小于 min，所以反转过程得到7为新的分钟，然后返回前一分钟)。作为任何不会引起变化的值，当前最小值大于当前最小值，你可以用来区分改变最小值的值和不改变最小值的值。

在使用固定大小整数的语言中，您从值的表示中借用了一点空间，因此它可能会溢出，断言将失败。但在其他情况下，它是常数的额外空间，所有操作仍然是 O (1)。

基于链表的堆栈有其他地方可以借用，例如 C 语言中下一个指针的最低有效位，或者 Java 中链表中对象的类型。对于 Java 来说，这意味着与连续堆栈相比使用了更多的空间，因为每个链接都有对象开销:

public class LinkedStackWithMin {
private static class Link {
final int value;
final Link next;


Link ( int value, Link next ) {
this.value = value;
this.next = next;
}


int pop ( LinkedStackWithMin stack ) {
stack.top = next;
return value;
}
}


private static class MinLink extends Link {
MinLink ( int value, Link next ) {
super( value, next );
}


int pop ( LinkedStackWithMin stack ) {
stack.top = next;
int prevMin = stack.min;
stack.min = value;
return prevMin;
}
}


Link top;
int min;


public LinkedStackWithMin () {
}


public void push ( int val ) {
if ( ( top == null ) || ( val < min ) ) {
top = new MinLink(min, top);
min = val;
} else {
top = new Link(val, top);
}
}


public int pop () {
return top.pop(this);
}


public int getMin () {
return min;
}


public boolean isEmpty () {
return top == null;
}

在 C 语言中，开销不存在，可以借用下一个指针的 lsb:

typedef struct _stack_link stack_with_min;


typedef struct _stack_link stack_link;


struct _stack_link {
size_t  next;
int     value;
};


stack_link* get_next ( stack_link* link )
{
return ( stack_link * )( link -> next & ~ ( size_t ) 1 );
}


bool is_min ( stack_link* link )
{
return ( link -> next & 1 ) ! = 0;
}


void push ( stack_with_min* stack, int value )
{
stack_link *link = malloc ( sizeof( stack_link ) );


link -> next = ( size_t ) stack -> next;


if ( (stack -> next == 0) || ( value == stack -> value ) ) {
link -> value = stack -> value;
link -> next |= 1; // mark as min
} else {
link -> value = value;
}


stack -> next = link;
}


etc.;

然而，这些都不是真正的 O (1)。它们在实践中不需要更多的空间，因为它们利用了这些语言中数字、对象或指针表示的漏洞。但是一个理论机器使用一个更紧凑的表示将需要额外的位被添加到该表示在每种情况下。

小开

I think only push operation suffers, is enough. My implementation includes a stack of nodes. Each node contain the data item and also the minimum on that moment. This minimum is updated each time a push operation is done.

以下是一些需要理解的要点:

我使用 LinkedList 实现了堆栈。
指针顶部总是指向最后一个推入的项目。如果堆栈顶部没有项，则为 NULL。
当推送一个项目时，将分配一个新节点，该节点有一个指向前一个堆栈的下一个指针，top 将更新为指向这个新节点。

与普通堆栈实现的唯一区别是，在 push 期间，它为新节点更新了一个成员 min。

为了便于演示，请看一下用 C + + 实现的代码。

/*
*  Implementation of Stack that can give minimum in O(1) time all the time
*  This solution uses same data structure for minimum variable, it could be implemented using pointers but that will be more space consuming
*/


#include <iostream>
using namespace std;


typedef struct stackLLNodeType stackLLNode;


struct stackLLNodeType {
int item;
int min;
stackLLNode *next;
};


class DynamicStack {
private:
int stackSize;
stackLLNode *top;


public:
DynamicStack();
~DynamicStack();
void push(int x);
int pop();
int getMin();
int size() { return stackSize; }
};


void pushOperation(DynamicStack& p_stackObj, int item);
void popOperation(DynamicStack& p_stackObj);


int main () {
DynamicStack stackObj;


pushOperation(stackObj, 3);
pushOperation(stackObj, 1);
pushOperation(stackObj, 2);
popOperation(stackObj);
popOperation(stackObj);
popOperation(stackObj);
popOperation(stackObj);
pushOperation(stackObj, 4);
pushOperation(stackObj, 7);
pushOperation(stackObj, 6);
popOperation(stackObj);
popOperation(stackObj);
popOperation(stackObj);
popOperation(stackObj);


return 0;
}


DynamicStack::DynamicStack() {
// initialization
stackSize = 0;
top = NULL;
}


DynamicStack::~DynamicStack() {
stackLLNode* tmp;
// chain memory deallocation to avoid memory leak
while (top) {
tmp = top;
top = top->next;
delete tmp;
}
}


void DynamicStack::push(int x) {
// allocate memory for new node assign to top
if (top==NULL) {
top = new stackLLNode;
top->item = x;
top->next = NULL;
top->min = top->item;
}
else {
// allocation of memory
stackLLNode *tmp = new stackLLNode;
// assign the new item
tmp->item = x;
tmp->next = top;


// store the minimum so that it does not get lost after pop operation of later minimum
if (x < top->min)
tmp->min = x;
else
tmp->min = top->min;


// update top to new node
top = tmp;
}
stackSize++;
}


int DynamicStack::pop() {
// check if stack is empty
if (top == NULL)
return -1;


stackLLNode* tmp = top;
int curItem = top->item;
top = top->next;
delete tmp;
stackSize--;
return curItem;
}


int DynamicStack::getMin() {
if (top == NULL)
return -1;
return top->min;
}
void pushOperation(DynamicStack& p_stackObj, int item) {
cout<<"Just pushed: "<<item<<endl;
p_stackObj.push(item);
cout<<"Current stack min: "<<p_stackObj.getMin()<<endl;
cout<<"Current stack size: "<<p_stackObj.size()<<endl<<endl;
}


void popOperation(DynamicStack& p_stackObj) {
int popItem = -1;
if ((popItem = p_stackObj.pop()) == -1 )
cout<<"Cannot pop. Stack is empty."<<endl;
else {
cout<<"Just popped: "<<popItem<<endl;
if (p_stackObj.getMin() == -1)
cout<<"No minimum. Stack is empty."<<endl;
else
cout<<"Current stack min: "<<p_stackObj.getMin()<<endl;
cout<<"Current stack size: "<<p_stackObj.size()<<endl<<endl;
}
}

程序的输出如下:

Just pushed: 3
Current stack min: 3
Current stack size: 1


Just pushed: 1
Current stack min: 1
Current stack size: 2


Just pushed: 2
Current stack min: 1
Current stack size: 3


Just popped: 2
Current stack min: 1
Current stack size: 2


Just popped: 1
Current stack min: 3
Current stack size: 1


Just popped: 3
No minimum. Stack is empty.
Current stack size: 0


Cannot pop. Stack is empty.
Just pushed: 4
Current stack min: 4
Current stack size: 1


Just pushed: 7
Current stack min: 4
Current stack size: 2


Just pushed: 6
Current stack min: 4
Current stack size: 3


Just popped: 6
Current stack min: 4
Current stack size: 2


Just popped: 7
Current stack min: 4
Current stack size: 1


Just popped: 4
No minimum. Stack is empty.
Current stack size: 0


Cannot pop. Stack is empty.

小开

Here is my Code which runs with O(1). The previous code which I posted had problem when the minimum element gets popped. I modified my code. This one uses another Stack that maintains minimum element present in stack above the current pushed element.

 class StackDemo
{
int[] stk = new int[100];
int top;
public StackDemo()
{
top = -1;
}
public void Push(int value)
{
if (top == 100)
Console.WriteLine("Stack Overflow");
else
stk[++top] = value;
}
public bool IsEmpty()
{
if (top == -1)
return true;
else
return false;
}
public int Pop()
{
if (IsEmpty())
{
Console.WriteLine("Stack Underflow");
return 0;
}
else
return stk[top--];
}
public void Display()
{
for (int i = top; i >= 0; i--)
Console.WriteLine(stk[i]);
}
}
class MinStack : StackDemo
{
int top;
int[] stack = new int[100];
StackDemo s1; int min;
public MinStack()
{
top = -1;
s1 = new StackDemo();
}
public void PushElement(int value)
{
s1.Push(value);
if (top == 100)
Console.WriteLine("Stack Overflow");
if (top == -1)
{
stack[++top] = value;
stack[++top] = value;
}
else
{
//  stack[++top]=value;
int ele = PopElement();
stack[++top] = ele;
int a = MininmumElement(min, value);
stack[++top] = min;


stack[++top] = value;
stack[++top] = a;




}
}
public int PopElement()
{


if (top == -1)
return 1000;
else
{
min = stack[top--];
return stack[top--];
}


}
public int PopfromStack()
{
if (top == -1)
return 1000;
else
{
s1.Pop();
return PopElement();
}
}
public int MininmumElement(int a,int b)
{
if (a > b)
return b;
else
return a;
}
public int StackTop()
{
return stack[top];
}
public void DisplayMinStack()
{
for (int i = top; i >= 0; i--)
Console.WriteLine(stack[i]);
}
}
class Program
{
static void Main(string[] args)
{
MinStack ms = new MinStack();
ms.PushElement(15);
ms.PushElement(2);
ms.PushElement(1);
ms.PushElement(13);
ms.PushElement(5);
ms.PushElement(21);
Console.WriteLine("Min Stack");
ms.DisplayMinStack();
Console.WriteLine("Minimum Element:"+ms.StackTop());
ms.PopfromStack();
ms.PopfromStack();
ms.PopfromStack();
ms.PopfromStack();


Console.WriteLine("Min Stack");
ms.DisplayMinStack();
Console.WriteLine("Minimum Element:" + ms.StackTop());
Thread.Sleep(1000000);
}
}

小开

我使用了一种不同的堆栈。

//
//  main.cpp
//  Eighth
//
//  Created by chaitanya on 4/11/13.
//  Copyright (c) 2013 cbilgika. All rights reserved.
//


#include <iostream>
#include <limits>
using namespace std;
struct stack
{
int num;
int minnum;
}a[100];


void push(int n,int m,int &top)
{


top++;
if (top>=100) {
cout<<"Stack Full";
cout<<endl;
}
else{
a[top].num = n;
a[top].minnum = m;
}




}


void pop(int &top)
{
if (top<0) {
cout<<"Stack Empty";
cout<<endl;
}
else{
top--;
}




}
void print(int &top)
{
cout<<"Stack: "<<endl;
for (int j = 0; j<=top ; j++) {
cout<<"("<<a[j].num<<","<<a[j].minnum<<")"<<endl;
}
}




void get_min(int &top)
{
if (top < 0)
{
cout<<"Empty Stack";
}
else{
cout<<"Minimum element is: "<<a[top].minnum;
}
cout<<endl;
}


int main()
{


int top = -1,min = numeric_limits<int>::min(),num;
cout<<"Enter the list to push (-1 to stop): ";
cin>>num;
while (num!=-1) {
if (top == -1) {
min = num;
push(num, min, top);
}
else{
if (num < min) {
min = num;
}
push(num, min, top);
}
cin>>num;
}
print(top);
get_min(top);
return 0;
}

产出:

Enter the list to push (-1 to stop): 5
1
4
6
2
-1
Stack:
(5,5)
(1,1)
(4,1)
(6,1)
(2,1)
Minimum element is: 1

Try it. I think it answers the question. The second element of every pair gives the minimum value seen when that element was inserted.

小开

public class MinStack<E>{


private final LinkedList<E> mainStack = new LinkedList<E>();
private final LinkedList<E> minStack = new LinkedList<E>();
private final Comparator<E> comparator;


public MinStack(Comparator<E> comparator)
{
this.comparator = comparator;
}


/**
* Pushes an element onto the stack.
*
*
* @param e the element to push
*/
public void push(E e) {
mainStack.push(e);
if(minStack.isEmpty())
{
minStack.push(e);
}
else if(comparator.compare(e, minStack.peek())<=0)
{
minStack.push(e);
}
else
{
minStack.push(minStack.peek());
}
}


/**
* Pops an element from the stack.
*
*
* @throws NoSuchElementException if this stack is empty
*/
public E pop() {
minStack.pop();
return  mainStack.pop();
}


/**
* Returns but not remove smallest element from the stack. Return null if stack is empty.
*
*/
public E getMinimum()
{
return minStack.peek();
}


@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("Main stack{");
for (E e : mainStack) {
sb.append(e.toString()).append(",");
}
sb.append("}");


sb.append(" Min stack{");
for (E e : minStack) {
sb.append(e.toString()).append(",");
}
sb.append("}");


sb.append(" Minimum = ").append(getMinimum());
return sb.toString();
}


public static void main(String[] args) {
MinStack<Integer> st = new MinStack<Integer>(Comparators.INTEGERS);


st.push(2);
Assert.assertTrue("2 is min in stack {2}", st.getMinimum().equals(2));
System.out.println(st);


st.push(6);
Assert.assertTrue("2 is min in stack {2,6}", st.getMinimum().equals(2));
System.out.println(st);


st.push(4);
Assert.assertTrue("2 is min in stack {2,6,4}", st.getMinimum().equals(2));
System.out.println(st);


st.push(1);
Assert.assertTrue("1 is min in stack {2,6,4,1}", st.getMinimum().equals(1));
System.out.println(st);


st.push(5);
Assert.assertTrue("1 is min in stack {2,6,4,1,5}", st.getMinimum().equals(1));
System.out.println(st);


st.pop();
Assert.assertTrue("1 is min in stack {2,6,4,1}", st.getMinimum().equals(1));
System.out.println(st);


st.pop();
Assert.assertTrue("2 is min in stack {2,6,4}", st.getMinimum().equals(2));
System.out.println(st);


st.pop();
Assert.assertTrue("2 is min in stack {2,6}", st.getMinimum().equals(2));
System.out.println(st);


st.pop();
Assert.assertTrue("2 is min in stack {2}", st.getMinimum().equals(2));
System.out.println(st);


st.pop();
Assert.assertTrue("null is min in stack {}", st.getMinimum()==null);
System.out.println(st);
}
}

小开

I am posting the complete code here to find min and max in a given stack.

Time complexity will be O(1)..

package com.java.util.collection.advance.datastructure;


/**
*
* @author vsinha
*
*/
public abstract interface Stack<E> {


/**
* Placing a data item on the top of the stack is called pushing it
* @param element
*
*/
public abstract void push(E element);




/**
* Removing it from the top of the stack is called popping it
* @return the top element
*/
public abstract E pop();


/**
* Get it top element from the stack and it
* but the item is not removed from the stack, which remains unchanged
* @return the top element
*/
public abstract E peek();


/**
* Get the current size of the stack.
* @return
*/
public abstract int size();




/**
* Check whether stack is empty of not.
* @return true if stack is empty, false if stack is not empty
*/
public abstract boolean empty();






}






package com.java.util.collection.advance.datastructure;


@SuppressWarnings("hiding")
public abstract interface MinMaxStack<Integer> extends Stack<Integer> {


public abstract int min();


public abstract int max();


}




package com.java.util.collection.advance.datastructure;


import java.util.Arrays;


/**
*
* @author vsinha
*
* @param <E>
*/
public class MyStack<E> implements Stack<E> {


private E[] elements =null;
private int size = 0;
private int top = -1;
private final static int DEFAULT_INTIAL_CAPACITY = 10;




public MyStack(){
// If you don't specify the size of stack. By default, Stack size will be 10
this(DEFAULT_INTIAL_CAPACITY);
}


@SuppressWarnings("unchecked")
public MyStack(int intialCapacity){
if(intialCapacity <=0){
throw new IllegalArgumentException("initial capacity can't be negative or zero");
}
// Can't create generic type array
elements =(E[]) new Object[intialCapacity];
}


@Override
public void push(E element) {
ensureCapacity();
elements[++top] = element;
++size;
}


@Override
public E pop() {
E element = null;
if(!empty()) {
element=elements[top];
// Nullify the reference
elements[top] =null;
--top;
--size;
}
return element;
}


@Override
public E peek() {
E element = null;
if(!empty()) {
element=elements[top];
}
return element;
}


@Override
public int size() {
return size;
}


@Override
public boolean empty() {
return size == 0;
}


/**
* Increases the capacity of this <tt>Stack by double of its current length</tt> instance,
* if stack is full
*/
private void ensureCapacity() {
if(size != elements.length) {
// Don't do anything. Stack has space.
} else{
elements = Arrays.copyOf(elements, size *2);
}
}


@Override
public String toString() {
return "MyStack [elements=" + Arrays.toString(elements) + ", size="
+ size + ", top=" + top + "]";
}




}




package com.java.util.collection.advance.datastructure;


/**
* Time complexity will be O(1) to find min and max in a given stack.
* @author vsinha
*
*/
public class MinMaxStackFinder extends MyStack<Integer> implements MinMaxStack<Integer> {


private MyStack<Integer> minStack;


private MyStack<Integer> maxStack;


public MinMaxStackFinder (int intialCapacity){
super(intialCapacity);
minStack =new MyStack<Integer>();
maxStack =new MyStack<Integer>();


}
public void push(Integer element) {
// Current element is lesser or equal than min() value, Push the current element in min stack also.
if(!minStack.empty()) {
if(min() >= element) {
minStack.push(element);
}
} else{
minStack.push(element);
}
// Current element is greater or equal than max() value, Push the current element in max stack also.
if(!maxStack.empty()) {
if(max() <= element) {
maxStack.push(element);
}
} else{
maxStack.push(element);
}
super.push(element);
}




public Integer pop(){
Integer curr = super.pop();
if(curr !=null) {
if(min() == curr) {
minStack.pop();
}


if(max() == curr){
maxStack.pop();
}
}
return curr;
}




@Override
public int min() {
return minStack.peek();
}


@Override
public int max() {
return maxStack.peek();
}




@Override
public String toString() {
return super.toString()+"\nMinMaxStackFinder [minStack=" + minStack + "\n maxStack="
+ maxStack + "]" ;
}








}


// You can use the below program to execute it.


package com.java.util.collection.advance.datastructure;


import java.util.Random;


public class MinMaxStackFinderApp {


public static void main(String[] args) {
MinMaxStack<Integer> stack =new MinMaxStackFinder(10);
Random random =new Random();
for(int i =0; i< 10; i++){
stack.push(random.nextInt(100));
}
System.out.println(stack);
System.out.println("MAX :"+stack.max());
System.out.println("MIN :"+stack.min());


stack.pop();
stack.pop();
stack.pop();
stack.pop();
stack.pop();


System.out.println(stack);
System.out.println("MAX :"+stack.max());
System.out.println("MIN :"+stack.min());
}
}

如果你遇到任何问题，请告诉我

谢谢, 维卡什

小开

#include<stdio.h>
struct stack
{
int data;
int mindata;
}a[100];


void push(int *tos,int input)
{
if (*tos > 100)
{
printf("overflow");
return;
}
(*tos)++;
a[(*tos)].data=input;
if (0 == *tos)
a[*tos].mindata=input;
else if (a[*tos -1].mindata < input)
a[*tos].mindata=a[*tos -1].mindata;
else
a[*tos].mindata=input;
}


int pop(int * tos)
{
if (*tos <= -1)
{
printf("underflow");
return -1;
}
return(a[(*tos)--].data);
}
void display(int tos)
{
while (tos > -1)
{
printf("%d:%d\t",a[tos].data,a[tos].mindata);
tos--;
}
}


int min(int tos)
{
return(a[tos].mindata);
}
int main()
{
int tos=-1,x,choice;
while(1)
{
printf("press 1-push,2-pop,3-mindata,4-display,5-exit ");
scanf("%d",&choice);
switch(choice)
{
case 1: printf("enter data to push");
scanf("%d",&x);
push(&tos,x);
break;
case 2: printf("the poped out data=%d ",pop(&tos));
break;
case 3: printf("The min peeped data:%d",min(tos));
break;
case 4: printf("The elements of stack \n");
display(tos);
break;
default: exit(0);
}
}

小开

I found this solution 给你

struct StackGetMin {
void push(int x) {
elements.push(x);
if (minStack.empty() || x <= minStack.top())
minStack.push(x);
}
bool pop() {
if (elements.empty()) return false;
if (elements.top() == minStack.top())
minStack.pop();
elements.pop();
return true;
}
bool getMin(int &min) {
if (minStack.empty()) {
return false;
} else {
min = minStack.top();
return true;
}
}
stack<int> elements;
stack<int> minStack;
};

小开

struct Node {
let data: Int
init(_ d:Int){
data = d
}
}


struct Stack {
private var backingStore = [Node]()
private var minArray = [Int]()


mutating func push(n:Node) {
backingStore.append(n)
minArray.append(n.data)
minArray.sort(>)
minArray
}


mutating func pop() -> Node? {
if(backingStore.isEmpty){
return nil
}


let n = backingStore.removeLast()


var found = false
minArray = minArray.filter{
if (!found && $0 == n.data) {
found = true
return false
}
return true
}
return n
}


func min() -> Int? {
return minArray.last
}
}

小开

public interface IMinStack<T extends Comparable<T>> {
public void push(T val);
public T pop();
public T minValue();
public int size();
}

import java.util.Stack;


public class MinStack<T extends Comparable<T>> implements IMinStack<T> {
private Stack<T> stack = new Stack<T>();
private Stack<T> minStack = new Stack<T>();


@Override
public void push(T val) {
stack.push(val);
if (minStack.isEmpty() || val.compareTo(minStack.peek()) < 0)
minStack.push(val);
}


@Override
public T pop() {
T val = stack.pop();
if ((false == minStack.isEmpty())
&& val.compareTo(minStack.peek()) == 0)
minStack.pop();
return val;
}


@Override
public T minValue() {
return minStack.peek();
}


@Override
public int size() {
return stack.size();
}
}

小开

我找到了一个满足所有提到的约束(常量时间操作)和 常数额外空间常数额外空间的解决方案。

其思想是存储最小值和输入数字之间的差异，并更新最小值，如果它不再是最小值。

守则如下:

public class MinStack {
long min;
Stack<Long> stack;


public MinStack(){
stack = new Stack<>();
}


public void push(int x) {
if (stack.isEmpty()) {
stack.push(0L);
min = x;
} else {
stack.push(x - min); //Could be negative if min value needs to change
if (x < min) min = x;
}
}


public int pop() {
if (stack.isEmpty()) return;


long pop = stack.pop();


if (pop < 0) {
long ret = min
min = min - pop; //If negative, increase the min value
return (int)ret;
}
return (int)(pop + min);


}


public int top() {
long top = stack.peek();
if (top < 0) {
return (int)min;
} else {
return (int)(top + min);
}
}


public int getMin() {
return (int)min;
}
}

提供者: https://leetcode.com/discuss/15679/share-my-java-solution-with-only-one-stack

小开

class MyStackImplementation{
private final int capacity = 4;
int min;
int arr[] = new int[capacity];
int top = -1;


public void push ( int val ) {
top++;
if(top <= capacity-1){
if(top == 0){
min = val;
arr[top] = val;
}
else if(val < min){
arr[top] = arr[top]+min;
min = arr[top]-min;
arr[top] = arr[top]-min;
}
else {
arr[top] = val;
}
System.out.println("element is pushed");
}
else System.out.println("stack is full");
}


public void pop () {
top--;
if(top > -1){
min = arr[top];
}
else {min=0; System.out.println("stack is under flow");}
}


public int min(){
return min;
}


public boolean isEmpty () {
return top == 0;
}


public static void main(String...s){
MyStackImplementation msi = new MyStackImplementation();
msi.push(1);
msi.push(4);
msi.push(2);
msi.push(10);
System.out.println(msi.min);
msi.pop();
msi.pop();
msi.pop();
msi.pop();
msi.pop();
System.out.println(msi.min);
}
}

小开

Here's the PHP implementation of what explained in Jon Skeet 的回答 as the slightly better space complexity implementation to get the maximum of stack in O(1).

<?php


/**
* An ordinary stack implementation.
*
* In real life we could just extend the built-in "SplStack" class.
*/
class BaseIntegerStack
{
/**
* Stack main storage.
*
* @var array
*/
private $storage = [];


// ------------------------------------------------------------------------
// Public API
// ------------------------------------------------------------------------


/**
* Pushes to stack.
*
* @param  int $value New item.
*
* @return bool
*/
public function push($value)
{
return is_integer($value)
? (bool) array_push($this->storage, $value)
: false;
}


/**
* Pops an element off the stack.
*
* @return int
*/
public function pop()
{
return array_pop($this->storage);
}


/**
* See what's on top of the stack.
*
* @return int|bool
*/
public function top()
{
return empty($this->storage)
? false
: end($this->storage);
}


// ------------------------------------------------------------------------
// Magic methods
// ------------------------------------------------------------------------


/**
* String representation of the stack.
*
* @return string
*/
public function __toString()
{
return implode('|', $this->storage);
}
} // End of BaseIntegerStack class


/**
* The stack implementation with getMax() method in O(1).
*/
class Stack extends BaseIntegerStack
{
/**
* Internal stack to keep track of main stack max values.
*
* @var BaseIntegerStack
*/
private $maxStack;


/**
* Stack class constructor.
*
* Dependencies are injected.
*
* @param BaseIntegerStack $stack Internal stack.
*
* @return void
*/
public function __construct(BaseIntegerStack $stack)
{
$this->maxStack = $stack;
}


// ------------------------------------------------------------------------
// Public API
// ------------------------------------------------------------------------


/**
* Prepends an item into the stack maintaining max values.
*
* @param  int $value New item to push to the stack.
*
* @return bool
*/
public function push($value)
{
if ($this->isNewMax($value)) {
$this->maxStack->push($value);
}


parent::push($value);
}


/**
* Pops an element off the stack maintaining max values.
*
* @return int
*/
public function pop()
{
$popped = parent::pop();


if ($popped == $this->maxStack->top()) {
$this->maxStack->pop();
}


return $popped;
}


/**
* Finds the maximum of stack in O(1).
*
* @return int
* @see push()
*/
public function getMax()
{
return $this->maxStack->top();
}


// ------------------------------------------------------------------------
// Internal helpers
// ------------------------------------------------------------------------


/**
* Checks that passing value is a new stack max or not.
*
* @param  int $new New integer to check.
*
* @return boolean
*/
private function isNewMax($new)
{
return empty($this->maxStack) OR $new > $this->maxStack->top();
}


} // End of Stack class


// ------------------------------------------------------------------------
// Stack Consumption and Test
// ------------------------------------------------------------------------
$stack = new Stack(
new BaseIntegerStack
);


$stack->push(9);
$stack->push(4);
$stack->push(237);
$stack->push(5);
$stack->push(556);
$stack->push(15);


print "Stack: $stack\n";
print "Max: {$stack->getMax()}\n\n";


print "Pop: {$stack->pop()}\n";
print "Pop: {$stack->pop()}\n\n";


print "Stack: $stack\n";
print "Max: {$stack->getMax()}\n\n";


print "Pop: {$stack->pop()}\n";
print "Pop: {$stack->pop()}\n\n";


print "Stack: $stack\n";
print "Max: {$stack->getMax()}\n";


// Here's the sample output:
//
// Stack: 9|4|237|5|556|15
// Max: 556
//
// Pop: 15
// Pop: 556
//
// Stack: 9|4|237|5
// Max: 237
//
// Pop: 5
// Pop: 237
//
// Stack: 9|4
// Max: 9

小开

class FastStack {


private static class StackNode {
private Integer data;
private StackNode nextMin;


public StackNode(Integer data) {
this.data = data;
}


public Integer getData() {
return data;
}


public void setData(Integer data) {
this.data = data;
}


public StackNode getNextMin() {
return nextMin;
}


public void setNextMin(StackNode nextMin) {
this.nextMin = nextMin;
}


}


private LinkedList<StackNode> stack = new LinkedList<>();


private StackNode currentMin = null;


public void push(Integer item) {
StackNode node = new StackNode(item);
if (currentMin == null) {
currentMin = node;
node.setNextMin(null);
} else if (item < currentMin.getData()) {
StackNode oldMinNode = currentMin;
node.setNextMin(oldMinNode);
currentMin = node;
}


stack.addFirst(node);
}


public Integer pop() {
if (stack.isEmpty()) {
throw new EmptyStackException();
}
StackNode node = stack.peek();
if (currentMin == node) {
currentMin = node.getNextMin();
}
stack.removeFirst();
return node.getData();
}


public Integer getMinimum() {
if (stack.isEmpty()) {
throw new NoSuchElementException("Stack is empty");
}
return currentMin.getData();
}
}

小开

这是我的代码，运行与 O (1)。在这里，我使用的向量对，其中包含的值推动，也包含最小值到这个推动值。

下面是我的 C + + 实现版本。

vector<pair<int,int> >A;
int sz=0; // to keep track of the size of vector


class MinStack
{
public:
MinStack()
{
A.clear();
sz=0;
}


void push(int x)
{
int mn=(sz==0)?x: min(A[sz-1].second,x); //find the minimum value upto this pushed value
A.push_back(make_pair(x,mn));
sz++; // increment the size
}


void pop()
{
if(sz==0) return;
A.pop_back(); // pop the last inserted element
sz--;  // decrement size
}


int top()
{
if(sz==0)   return -1;  // if stack empty return -1
return A[sz-1].first;  // return the top element
}


int getMin()
{
if(sz==0) return -1;
return A[sz-1].second; // return the minimum value at sz-1
}
};

小开

    **The task can be acheived by creating two stacks:**






import java.util.Stack;
/*
*
* Find min in stack using O(n) Space Complexity
*/
public class DeleteMinFromStack {


void createStack(Stack<Integer> primary, Stack<Integer> minStack, int[] arr) {
/* Create main Stack and in parallel create the stack which contains the minimum seen so far while creating main Stack */
primary.push(arr[0]);
minStack.push(arr[0]);


for (int i = 1; i < arr.length; i++) {
primary.push(arr[i]);
if (arr[i] <= minStack.peek())// Condition to check to push the value in minimum stack only when this urrent value is less than value seen at top of this stack */
minStack.push(arr[i]);
}


}


int findMin(Stack<Integer> secStack) {
return secStack.peek();
}


public static void main(String args[]) {


Stack<Integer> primaryStack = new Stack<Integer>();
Stack<Integer> minStack = new Stack<Integer>();


DeleteMinFromStack deleteMinFromStack = new DeleteMinFromStack();


int[] arr = { 5, 5, 6, 8, 13, 1, 11, 6, 12 };
deleteMinFromStack.createStack(primaryStack, minStack, arr);
int mimElement = deleteMinFromStack.findMin(primaryStack, minStack);
/** This check for algorithm when the main Stack Shrinks by size say i as in loop below */
for (int i = 0; i < 2; i++) {
primaryStack.pop();
}


System.out.println(" Minimum element is " + mimElement);
}


}
/*
here in have tried to add for loop wherin the main tack can be shrinked/expaned so we can check the algorithm */

小开

在用户设计对象堆栈中寻找最小值的一个实际实现, 学校

Stack 将根据分配给特定区域的学校的排名来存储 Stack 中的学校，比如 findMin ()给出了我们获得最大入学申请数的学校，这反过来由比较器定义，比较器使用与前一季学校相关的排名。

The Code for same is below:




package com.practical;


import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;


public class CognitaStack {


public School findMin(Stack<School> stack, Stack<School> minStack) {


if (!stack.empty() && !minStack.isEmpty())
return (School) minStack.peek();
return null;
}


public School removeSchool(Stack<School> stack, Stack<School> minStack) {


if (stack.isEmpty())
return null;
School temp = stack.peek();
if (temp != null) {
// if(temp.compare(stack.peek(), minStack.peek())<0){
stack.pop();
minStack.pop();
// }


// stack.pop();
}
return stack.peek();
}


public static void main(String args[]) {


Stack<School> stack = new Stack<School>();
Stack<School> minStack = new Stack<School>();


List<School> lst = new LinkedList<School>();


School s1 = new School("Polam School", "London", 3);
School s2 = new School("AKELEY WOOD SENIOR SCHOOL", "BUCKINGHAM", 4);
School s3 = new School("QUINTON HOUSE SCHOOL", "NORTHAMPTON", 2);
School s4 = new School("OAKLEIGH HOUSE SCHOOL", " SWANSEA", 5);
School s5 = new School("OAKLEIGH-OAK HIGH SCHOOL", "Devon", 1);
School s6 = new School("BritishInter2", "Devon", 7);


lst.add(s1);
lst.add(s2);
lst.add(s3);
lst.add(s4);
lst.add(s5);
lst.add(s6);


Iterator<School> itr = lst.iterator();
while (itr.hasNext()) {
School temp = itr.next();
if ((minStack.isEmpty()) || (temp.compare(temp, minStack.peek()) < 0)) { // minStack.peek().equals(temp)
stack.push(temp);
minStack.push(temp);
} else {
minStack.push(minStack.peek());
stack.push(temp);
}


}


CognitaStack cogStack = new CognitaStack();
System.out.println(" Minimum in Stack is " + cogStack.findMin(stack, minStack).name);
cogStack.removeSchool(stack, minStack);
cogStack.removeSchool(stack, minStack);


System.out.println(" Minimum in Stack is "
+ ((cogStack.findMin(stack, minStack) != null) ? cogStack.findMin(stack, minStack).name : "Empty"));
}


}

此外，学校的宗旨如下:

package com.practical;


import java.util.Comparator;


public class School implements Comparator<School> {


String name;
String location;
int rank;


public School(String name, String location, int rank) {
super();
this.name = name;
this.location = location;
this.rank = rank;
}


@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((location == null) ? 0 : location.hashCode());
result = prime * result + ((name == null) ? 0 : name.hashCode());
result = prime * result + rank;
return result;
}


@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
School other = (School) obj;
if (location == null) {
if (other.location != null)
return false;
} else if (!location.equals(other.location))
return false;
if (name == null) {
if (other.name != null)
return false;
} else if (!name.equals(other.name))
return false;
if (rank != other.rank)
return false;
return true;
}


public String getName() {
return name;
}


public void setName(String name) {
this.name = name;
}


public String getLocation() {
return location;
}


public void setLocation(String location) {
this.location = location;
}


public int getRank() {
return rank;
}


public void setRank(int rank) {
this.rank = rank;
}


public int compare(School o1, School o2) {
// TODO Auto-generated method stub
return o1.rank - o2.rank;
}


}


class SchoolComparator implements Comparator<School> {


public int compare(School o1, School o2) {
return o1.rank - o2.rank;
}


}

这个例子包括以下内容: 1. 用户定义对象堆栈的实现 2. 使用要比较的 Object 的所有字段实现 hashcode ()和 equals ()方法 3.对于我们要求获取 Stack 的场景的一个实际实现包含按 O (1)顺序的操作

小开

下面是 Jon Skeets Answer的 C + + 实现。它可能不是实现它的最佳方式，但它确实做了它应该做的事情。

class Stack {
private:
struct stack_node {
int val;
stack_node *next;
};
stack_node *top;
stack_node *min_top;
public:
Stack() {
top = nullptr;
min_top = nullptr;
}
void push(int num) {
stack_node *new_node = nullptr;
new_node = new stack_node;
new_node->val = num;


if (is_empty()) {
top = new_node;
new_node->next = nullptr;


min_top = new_node;
new_node->next = nullptr;
} else {
new_node->next = top;
top = new_node;


if (new_node->val <= min_top->val) {
new_node->next = min_top;
min_top = new_node;
}
}
}


void pop(int &num) {
stack_node *tmp_node = nullptr;
stack_node *min_tmp = nullptr;


if (is_empty()) {
std::cout << "It's empty\n";
} else {
num = top->val;
if (top->val == min_top->val) {
min_tmp = min_top->next;
delete min_top;
min_top = min_tmp;
}
tmp_node = top->next;
delete top;
top = tmp_node;
}
}


bool is_empty() const {
return !top;
}


void get_min(int &item) {
item = min_top->val;
}
};

这是这个班的司机

int main() {
int pop, min_el;
Stack my_stack;


my_stack.push(4);
my_stack.push(6);
my_stack.push(88);
my_stack.push(1);
my_stack.push(234);
my_stack.push(2);


my_stack.get_min(min_el);
cout << "Min: " << min_el << endl;


my_stack.pop(pop);
cout << "Popped stock element: " << pop << endl;


my_stack.pop(pop);
cout << "Popped stock element: " << pop << endl;


my_stack.pop(pop);
cout << "Popped stock element: " << pop << endl;


my_stack.get_min(min_el);
cout << "Min: " << min_el << endl;


return 0;
}

Output:

Min: 1
Popped stock element: 2
Popped stock element: 234
Popped stock element: 1
Min: 4

小开

我们可以在 O (n)时间和 O (1)空间复杂度下完成这个任务，如下所示:

class MinStackOptimized:
def __init__(self):
self.stack = []
self.min = None


def push(self, x):
if not self.stack:
# stack is empty therefore directly add
self.stack.append(x)
self.min = x
else:
"""
Directly add (x-self.min) to the stack. This also ensures anytime we have a
negative number on the stack is when x was less than existing minimum
recorded thus far.
"""
self.stack.append(x-self.min)
if x < self.min:
# Update x to new min
self.min = x


def pop(self):
x = self.stack.pop()
if x < 0:
"""
if popped element was negative therefore this was the minimum
element, whose actual value is in self.min but stored value is what
contributes to get the next min. (this is one of the trick we use to ensure
we are able to get old minimum once current minimum gets popped proof is given
below in pop method), value stored during push was:
(x - self.old_min) and self.min = x therefore we need to backtrack
these steps self.min(current) - stack_value(x) actually implies to
x (self.min) - (x - self.old_min)
which therefore gives old_min back and therefore can now be set
back as current self.min.
"""
self.min = self.min - x


def top(self):
x = self.stack[-1]
if x < 0:
"""
As discussed above anytime there is a negative value on stack, this
is the min value so far and therefore actual value is in self.min,
current stack value is just for getting the next min at the time
this gets popped.
"""
return self.min
else:
"""
if top element of the stack was positive then it's simple, it was
not the minimum at the time of pushing it and therefore what we did
was x(actual) - self.min(min element at current stage) let's say `y`
therefore we just need to reverse the process to get the actual
value. Therefore self.min + y, which would translate to
self.min + x(actual) - self.min, thereby giving x(actual) back
as desired.
"""
return x + self.min


def getMin(self):
# Always self.min variable holds the minimum so for so easy peezy.
return self.min

小开

You could extend your original stack class and just add the min tracking to it. Let the original parent class handle everything else as usual.

public class StackWithMin extends Stack<Integer> {


private Stack<Integer> min;


public StackWithMin() {
min = new Stack<>();
}


public void push(int num) {
if (super.isEmpty()) {
min.push(num);
} else if (num <= min.peek()) {
min.push(num);
}
super.push(num);
}


public int min() {
return min.peek();
}


public Integer pop() {
if (super.peek() == min.peek()) {
min.pop();
}
return super.pop();
}
}

小开

我认为您可以简单地在堆栈实现中使用 LinkedList。

第一次推送一个值时，将该值作为 linkedlist 的头部。

然后每次推送一个值时，如果新值 < head.data，执行一个 prepand 操作(这意味着 head 变成了新值)

if not, then make an append operation.

当执行 pop ()时，检查 min = = linkedlist.head.data，如果是，则检查 head = head.next;

这是我的密码。

public class Stack {


int[] elements;
int top;
Linkedlists min;


public Stack(int n) {
elements = new int[n];
top = 0;
min = new Linkedlists();
}


public void realloc(int n) {
int[] tab = new int[n];
for (int i = 0; i < top; i++) {
tab[i] = elements[i];
}


elements = tab;
}


public void push(int x) {
if (top == elements.length) {
realloc(elements.length * 2);
}
if (top == 0) {
min.pre(x);
} else if (x < min.head.data) {
min.pre(x);
} else {
min.app(x);
}
elements[top++] = x;
}


public int pop() {


int x = elements[--top];
if (top == 0) {


}
if (this.getMin() == x) {
min.head = min.head.next;
}
elements[top] = 0;
if (4 * top < elements.length) {
realloc((elements.length + 1) / 2);
}


return x;
}


public void display() {
for (Object x : elements) {
System.out.print(x + " ");
}


}


public int getMin() {
if (top == 0) {
return 0;
}
return this.min.head.data;
}


public static void main(String[] args) {
Stack stack = new Stack(4);
stack.push(2);
stack.push(3);
stack.push(1);
stack.push(4);
stack.push(5);
stack.pop();
stack.pop();
stack.pop();
stack.push(1);
stack.pop();
stack.pop();
stack.pop();
stack.push(2);
System.out.println(stack.getMin());
stack.display();


}


}

小开

这里是我的解决方案在 java 中使用喜欢的列表。

class Stack{
int min;
Node top;
static class Node{
private int data;
private Node next;
private int min;


Node(int data, int min){
this.data = data;
this.min = min;
this.next = null;
}
}


void push(int data){
Node temp;
if(top == null){
temp = new Node(data,data);
top = temp;
top.min = data;
}
if(top.min > data){
temp = new Node(data,data);
temp.next = top;
top = temp;
} else {
temp = new Node(data, top.min);
temp.next = top;
top = temp;
}
}


void pop(){
if(top != null){
top = top.next;
}
}


int min(){
return top.min;
}

}

小开

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;


namespace Solution
{
public class MinStack
{
public MinStack()
{
MainStack=new Stack<int>();
Min=new Stack<int>();
}


static Stack<int> MainStack;
static Stack<int> Min;


public void Push(int item)
{
MainStack.Push(item);


if(Min.Count==0 || item<Min.Peek())
Min.Push(item);
}


public void Pop()
{
if(Min.Peek()==MainStack.Peek())
Min.Pop();
MainStack.Pop();
}
public int Peek()
{
return MainStack.Peek();
}


public int GetMin()
{
if(Min.Count==0)
throw new System.InvalidOperationException("Stack Empty");
return Min.Peek();
}
}
}

小开

Saw a brilliant solution here: Https://www.geeksforgeeks.org/design-a-stack-that-supports-getmin-in-o1-time-and-o1-extra-space/

Bellow 是我通过下面的算法编写的 Python 代码:

class Node:
def __init__(self, value):
self.value = value
self.next = None


class MinStack:
def __init__(self):
self.head = None
self.min = float('inf')


# @param x, an integer
def push(self, x):
if self.head == None:
self.head = Node(x)
self.min = x
else:
if x >= self.min:
n = Node(x)
n.next = self.head
self.head = n
else:
v = 2 * x - self.min
n = Node(v)
n.next = self.head
self.head = n
self.min = x


# @return nothing
def pop(self):
if self.head:
if self.head.value < self.min:
self.min = self.min * 2 - self.head.value
self.head = self.head.next


# @return an integer
def top(self):
if self.head:
if self.head.value < self.min:
self.min = self.min * 2 - self.head.value
return self.min
else:
return self.head.value
else:
return -1


# @return an integer
def getMin(self):
if self.head:
return self.min
else:
return -1

小开

To getMin elements from Stack. We have to use Two stack .i.e Stack s1 and Stack s2.

最初，两个堆栈都是空的，因此向两个堆栈添加元素

——————————递归地调用步骤2到4——————————

如果新元素添加到堆栈 s1中，则从堆栈 s2中弹出元素
将新元素与 s2进行比较，哪个元素更小，推到 s2。
从堆栈 s2中弹出(包含 min 元素)

代码是这样的:

package Stack;
import java.util.Stack;
public class  getMin
{


Stack<Integer> s1= new Stack<Integer>();
Stack<Integer> s2 = new Stack<Integer>();


void push(int x)
{
if(s1.isEmpty() || s2.isEmpty())


{
s1.push(x);
s2.push(x);
}
else
{


s1. push(x);
int y = (Integer) s2.pop();
s2.push(y);
if(x < y)
s2.push(x);
}
}
public Integer pop()
{
int x;
x=(Integer) s1.pop();
s2.pop();
return x;


}
public  int getmin()
{
int x1;
x1= (Integer)s2.pop();
s2.push(x1);
return x1;
}


public static void main(String[] args) {
getMin s = new getMin();
s.push(10);
s.push(20);
s.push(30);
System.out.println(s.getmin());
s.push(1);
System.out.println(s.getmin());
}


}

小开

假设我们要处理的堆栈是这样的:

6 , minvalue=2
2 , minvalue=2
5 , minvalue=3
3 , minvalue=3
9 , minvalue=7
7 , minvalue=7
8 , minvalue=8

在上面的表示中，堆栈只是由左值构建的，而右值的[ minvalue ]只是为了说明而写的，它将存储在一个变量中。

actual problem是当最小值被删除的时候: 在这一点上，我们如何知道下一个最小元素是什么，而不需要在堆栈上迭代。

例如，在我们的堆栈中，当6被弹出时，我们知道，这不是最小元素，因为最小元素是2，所以我们可以安全地删除它，而不需要更新我们的 min 值。

但是当我们弹出2时，我们可以看到最小值现在是2，如果这个弹出，那么我们需要将最小值更新为3。

Point1:

现在，如果您仔细观察，我们需要从这个特定的状态[2，minvalue = 2]生成 minvalue = 3。
或者，如果您深入到堆栈中，我们需要从这个特定的状态[3，minvalue = 3]生成 minvalue = 7
或者，如果您在堆栈中继续深入，那么我们需要从这个特定的状态[7，minvalue = 7]生成 minvalue = 8

你有没有注意到上述三个案例中有什么共同点？我们需要生成的值取决于两个相等的变量。没错。
为什么会发生这种情况，因为当我们推送一个比当前 minvalue 小的元素时，我们基本上就是推送堆栈中的这个元素，同时也更新了 minvalue 中的相同数字。

第二点:

因此，我们基本上是存储相同数字的重复一次在堆栈和一次在小数变量。
我们需要集中精力避免这种重复，并将一些有用的数据存储在堆栈或小值中，以生成前面的最小值，如上面的 CASES 所示。

让我们关注一下，当 push 中要存储的值小于最小值时，我们应该在堆栈中存储什么。让我们把这个变量命名为 y，现在我们的堆栈看起来像这样:

6 , minvalue=2
y1 , minvalue=2
5 , minvalue=3
y2 , minvalue=3
9 , minvalue=7
y3 , minvalue=7
8 , minvalue=8

我将它们重命名为 y1，y2，y3，以避免混淆，因为它们都具有相同的值。

Point3:

现在让我们尝试找到一些约束在 y1，y2和 y3之上。还记得我们在执行 pop ()时需要更新 minvalue 的确切时间吗? 只有当我们弹出与 minvalue 相等的元素时才需要更新 minvalue。
If we pop something greater than the minvalue then we don't have to update minvalue.
因此，要触发 minvalue 的更新，y1、 y2和 y3应该小于相应的 minvalue。[我们正在避免相等以避免重复[ Point2]]
so the constrain is [ y < minValue ].

Now let's come back to populate y, we need to generate some value and put y at the time of push, remember.
Let's take the value which is coming for push to be x which is less that the prevMinvalue, and the value which we will actually push in stack to be y.
所以有一点很明显 newMinValue = x 和 y < newMinValue。

现在我们需要计算 y (记住 y 可以是任何小于 newMinValue (x)的数字，所以我们需要找到一些能满足我们约束的数字) ，借助于 preMvalue 和 x (newMvalue)。

Let's do the math:
x < prevMinvalue [Given]
x - prevMinvalue < 0
x - prevMinValue + x < 0 + x [Add x on both side]
2*x - prevMinValue < x
this is the y which we were looking for less than x(newMinValue).
y = 2*x - prevMinValue. 'or' y = 2*newMinValue - prevMinValue 'or' y = 2*curMinValue - prevMinValue [taking curMinValue=newMinValue].

所以在推 x 的时候，如果它小于 preMinValue，那么我们推 y [2 * x-preMinValue ]并更新 newMinValue = x。

在弹出时，如果堆栈中包含的值小于 minValue，那么这就是我们更新 minValue 的触发器。我们必须从 curMinValue 和 y 计算 preMinValue。
Y = 2 * curMinValue-provMinValue [ Proved ]
PrevMinValue = 2 * curMinvalue-y.

2*curMinValue - y is the number which we need to update now to the prevMinValue.

相同逻辑的代码在下面与 O (1)时间和 O (1)空间复杂度共享。

// C++ program to implement a stack that supports
// getMinimum() in O(1) time and O(1) extra space.
#include <bits/stdc++.h>
using namespace std;
  

// A user defined stack that supports getMin() in
// addition to push() and pop()
struct MyStack
{
stack<int> s;
int minEle;
  

// Prints minimum element of MyStack
void getMin()
{
if (s.empty())
cout << "Stack is empty\n";
  

// variable minEle stores the minimum element
// in the stack.
else
cout <<"Minimum Element in the stack is: "
<< minEle << "\n";
}
  

// Prints top element of MyStack
void peek()
{
if (s.empty())
{
cout << "Stack is empty ";
return;
}
  

int t = s.top(); // Top element.
  

cout << "Top Most Element is: ";
  

// If t < minEle means minEle stores
// value of t.
(t < minEle)? cout << minEle: cout << t;
}
  

// Remove the top element from MyStack
void pop()
{
if (s.empty())
{
cout << "Stack is empty\n";
return;
}
  

cout << "Top Most Element Removed: ";
int t = s.top();
s.pop();
  

// Minimum will change as the minimum element
// of the stack is being removed.
if (t < minEle)
{
cout << minEle << "\n";
minEle = 2*minEle - t;
}
  

else
cout << t << "\n";
}
  

// Removes top element from MyStack
void push(int x)
{
// Insert new number into the stack
if (s.empty())
{
minEle = x;
s.push(x);
cout <<  "Number Inserted: " << x << "\n";
return;
}
  

// If new number is less than minEle
if (x < minEle)
{
s.push(2*x - minEle);
minEle = x;
}
  

else
s.push(x);
  

cout <<  "Number Inserted: " << x << "\n";
}
};
  

// Driver Code
int main()
{
MyStack s;
s.push(3);
s.push(5);
s.getMin();
s.push(2);
s.push(1);
s.getMin();
s.pop();
s.getMin();
s.pop();
s.peek();
  

return 0;
}

小开

我有更好的解决方案，在没有额外空间的情况下，使用 O (1)时间，您需要将元素作为字符串按下，例如 < first _ value，limit _ value > 。例如，查找这个字符串堆栈。

1,1

一，一

二，二

| 5,3 |

三，三

现在您总是可以在当前实例中找到 min 值，只需要查看并检查给定实例中的 min 值即可。这是没有额外空间的 O (1)时间