Подтвердить что ты не робот

Создайте стек таким образом, чтобы getMinimum() должен быть O (1)

Это один из вопросов интервью. Вам нужно создать стек, который содержит целочисленное значение, так что функция getMinimum() должна возвращать минимальный элемент в стеке.

Например: рассмотрим приведенный ниже пример

case #1

5  --> TOP
1
4
6
2

When getMinimum() is called it should return 1, which is the minimum element 
in the stack. 

case #2

stack.pop()
stack.pop()

Note: Both 5 and 1 are poped out of the stack. So after this, the stack
looks like,

4  --> TOP
6
2

When getMinimum() is called is should return 2 which is the minimum in the 
stack.

Constriants:

  • getMinimum должен вернуть минимальное значение в O (1)
  • Ограничение пространства также необходимо учитывать при его разработке, и если вы используете дополнительное пространство, оно должно быть постоянным.
4b9b3361

ОТВЕТЫ

Ответ 1

РЕДАКТОР: Это не соответствует ограничению "постоянного пространства" - оно в основном удваивает требуемое пространство. Я очень сомневаюсь, что есть решение, которое этого не делает, но без разрушения сложности выполнения (например, push/pop O (n)). Обратите внимание, что это не меняет сложность требуемого пространства, например. если у вас есть стек с требованиями O (n), это будет по-прежнему O (n) только с другим постоянным фактором.

Непостоянное пространство

Храните "дублированный" стек "минимум всех значений ниже в стеке". Когда вы вытащите основной стек, также вытащите мини-стек. Когда вы нажимаете основной стек, нажимайте либо новый элемент, либо текущий мин, в зависимости от того, что меньше. 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

Пожалуйста, дайте мне знать, если этого недостаточно. Это просто, когда вы его проверяете, но сначала может потребоваться немного поцарапать голову:)

(Конечно, недостатком является то, что он удваивает требования к пространству. Время выполнения не очень сильно страдает, т.е. оно остается той же сложностью.)

РЕДАКТИРОВАТЬ: Там вариант, который немного более странно, но имеет лучшее пространство в целом. У нас все еще есть минимальный стек, но мы только выходим из него, когда значение, которое мы выкладываем из основного стека, равно тому, которое находится в мини-стеке. Мы только нажимаем на мини-стек, когда значение, которое нажимается на основной стек, меньше или равно текущему минимальному значению. Это позволяет использовать удвоенные значения 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

Это заканчивается тем же самым сложным сложным пространством (в два раза больше исходного стека), но гораздо лучше используется пространство, если мы редко получаем "новый минимум или равный".

EDIT: Здесь реализована схема зла Пит. Я не тестировал его полностью, но я думаю, что все в порядке:)

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;
    }
}

Ответ 2

Добавьте поле для сохранения минимального значения и обновите его во время Pop() и Push(). Таким образом, getMinimum() будет O (1), но Pop() и Push() должны будут немного поработать.

Если будет выведено минимальное значение, Pop() будет O (n), в противном случае они будут оба равны O (1). При изменении размера Push() становится O (n) в соответствии с реализацией стека.

Вот быстрая реализация

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; } }
}

Ответ 3

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 для нового min, затем возвращает предыдущий мин). Поскольку любое значение, которое не вызывает изменения, текущий минимум больше текущего минимума, у вас есть что-то, что можно использовать для различия между значениями, которые изменяют минимум, и теми, которые этого не делают.

В языках, использующих целые числа фиксированного размера, вы заимствуете немного пространства из представления значений, поэтому он может переполняться и утверждение будет терпеть неудачу. Но в остальном это постоянное дополнительное пространство, и все операции все еще 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). На практике они не требуют больше места, поскольку они используют дыры в представлениях чисел, объектов или указателей на этих языках. Но теоретическая машина, которая использовала более компактное представление, потребовала бы добавления дополнительного бита в это представление в каждом случае.

Ответ 4

Я нашел решение, которое удовлетворяет всем упомянутым ограничениям (операции с постоянным временем) и постоянное дополнительное пространство.

Идея состоит в том, чтобы сохранить разницу между минимальным значением и номером ввода и обновить минимальное значение, если оно больше не является минимальным.

Код выглядит следующим образом:

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

Ответ 5

Ну, каковы ограничения времени выполнения push и pop? Если они не обязательно должны быть постоянными, то просто вычислите минимальное значение в этих двух операциях (делая их O (n)). В противном случае я не вижу, как это можно сделать с постоянным дополнительным пространством.

Ответ 6

Вот мой код, который работает с O (1). Предыдущий код, который я опубликовал, имел проблему при получении минимального элемента. Я изменил свой код. Этот использует другой стек, который поддерживает минимальный элемент, присутствующий в стеке над текущим толкаемым элементом.

 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);
    }
}

Ответ 7

Я использовал другой тип стека. Вот реализация.

//
//  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

Попробуйте. Я думаю, что он отвечает на вопрос. Второй элемент каждой пары дает минимальное значение, наблюдаемое при вставке этого элемента.

Ответ 8

Я размещаю полный код здесь, чтобы найти min и max в заданном стеке.

Сложность времени будет равна 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());
    }
}

Сообщите мне, если вы столкнулись с какой-либо проблемой

Спасибо, Vikash

Ответ 9

Вы можете расширить свой исходный класс стека и просто добавить к нему минимальное отслеживание. Пусть исходный родительский класс обрабатывает все остальное, как обычно.

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();
    }   
}

Ответ 10

Вот мое решение в 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;
  }

}

Ответ 11

Вот моя версия реализации.

 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;
        }
 }

Ответ 12

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);
    }
}

Ответ 13

#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);
}
}

Ответ 14

Я нашел это решение здесь

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;
};

Ответ 15

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
    }
}

Ответ 16

 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);

}
}

Ответ 17

Здесь PHP-реализация того, что объясняется в Jon Skeet, отвечает как немного более эффективная реализация сложности пространства, чтобы получить максимум стека в 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 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 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

Ответ 18

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();
    }
}

Ответ 19

Вот мой код, который работает с O (1). Здесь я использовал векторную пару, которая содержит значение, которое подталкивает и также содержит минимальное значение до этого вытолкнутого значения.


Вот моя версия реализации на С++.

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 
    }
};

Ответ 20

    **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 */

Ответ 21

Практическая реализация для поиска минимума в стеке пользовательского объекта, имя: Школа

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. Реализация метода hashcode() и equals(), использующего все поля Объектов для сравнения 3. Практическая реализация сценария, в котором мы rqeuire для получения Stack содержит операцию в порядке O (1)

Ответ 22

Вот реализация С++ для Jon Skeets Отвечать. Это может быть не самый оптимальный способ его реализации, но он делает именно то, что он должен был.

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 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;
}

Вывод:

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

Ответ 23

Мы можем делать это в 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 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 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

Ответ 24

Я думаю, вы можете просто использовать LinkedList в реализации вашего стека.

В первый раз, когда вы нажимаете значение, вы ставите это значение в качестве заголовка связанного списка.

то каждый раз, когда вы нажимаете значение, если новое значение < head.data, сделайте операцию preand (что означает, что голова станет новым значением)

если нет, затем выполните операцию добавления.

Когда вы создаете 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();

}

 }

Ответ 25

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();
        }
    }
}

Ответ 26

Увидел блестящее решение здесь: https://www.geeksforgeeks.org/design-a-stack-that-supports-getmin-in-o1-time-and-o1-extra-space/

Ниже приведен код 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

Ответ 27

Получить элементы из стека. Мы должны использовать два стека .ie стека s1 и стека s2.

  1. Изначально оба стека пусты, поэтому добавьте элементы в оба стека.

---------------------Recursively вызовите Шаг 2 - 4-----------------------

  1. Если новый элемент добавлен в стек s1.Затем поп элементы из стека s2

  2. сравнить новые элементы с s2. какой из них меньше, нажмите на s2.

  3. pop из стека 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());
        }

}

Ответ 28

Предположим, что стек, над которым мы будем работать, это:

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

В вышеприведенном представлении стек строится только по левому значению, правое значение [minvalue] записывается только в целях иллюстрации, которое будет храниться в одной переменной.

Проблема в том, что когда значение, являющееся минимальным значением, удаляется в этот момент, как мы можем узнать, каков следующий минимальный элемент, без итерации по стеку.

Как, например, в нашем стеке, когда выпало 6, мы знаем, что это не минимальный элемент, потому что минимальный элемент равен 2, поэтому мы можем безопасно удалить его, не обновляя наше минимальное значение.

Но когда мы выскакиваем 2, мы видим, что минимальное значение равно 2 прямо сейчас, и если оно выскочило, нам нужно обновить минимальное значение до 3.

Point1:

Теперь, если вы внимательно наблюдаете, нам нужно сгенерировать minvalue = 3 из этого конкретного состояния [2, minvalue = 2]. или если вы углубитесь в стек, нам нужно сгенерировать minvalue = 7 из этого конкретного состояния [3, minvalue = 3], или если вы пойдете еще глубже в стеке, то нам нужно сгенерировать minvalue = 8 из этого конкретного состояния [7, minvalue = 7]

Заметили ли вы что-то общее во всех вышеупомянутых 3 случаях, значение, которое нам нужно сгенерировать, зависит от двух переменных, которые оба равны. Правильный. Почему это происходит, потому что когда мы помещаем какой-то элемент меньше текущего минимального значения, то мы в основном помещаем этот элемент в стек и также обновляем то же число в минимальном значении.

Point2:

Таким образом, мы в основном храним дубликаты одного и того же числа один раз в стеке и один раз в переменной minvalue. Нам нужно сосредоточиться на том, чтобы избежать этого дублирования и хранить что-то полезное в стеке или в минимальном значении, чтобы сгенерировать предыдущий минимум, как показано в CASES выше.

Давайте сосредоточимся на том, что мы должны хранить в стеке, когда значение для сохранения в push меньше, чем minmumvalue. Назовите эту переменную 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. Помните ли вы, когда именно нам нужно обновить minvalue при выполнении pop(), только когда мы выдвинули элемент, равный minvalue. Если мы добавляем что-то большее, чем minvalue, нам не нужно обновлять minvalue. Таким образом, чтобы запустить обновление minvalue, y1, y2 & y3 должны быть меньше, чем соответствующее minvalue. [Мы избегаем дублирования, чтобы избежать дублирования [Point2]], поэтому ограничение равно [y <minValue].

Теперь давайте вернемся к заполнению y, нам нужно сгенерировать какое-то значение и поставить y во время нажатия, запомните. Давайте возьмем значение, которое придет для push, равным x, которое меньше значения prevMinvalue, и значение, которое мы фактически поместим в стек, будет y. Таким образом, очевидно, что newMinValue = x, а y <newMinvalue.

Теперь нам нужно вычислить y (помните, что y может быть любым числом, которое меньше newMinValue (x), поэтому нам нужно найти некоторое число, которое может удовлетворить наше ограничение) с помощью prevMinvalue и x (newMinvalue).

Let 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, если оно меньше значения prevMinvalue, мы нажимаем y [2 * x-prevMinValue] и обновляем newMinValue = x.

И во время всплывающего окна, если в стеке содержится что-то меньшее, чем minValue, тогда наш триггер обновляет minVAlue. Мы должны вычислить prevMinValue из curMinValue и y. y = 2 * curMinValue - prevMinValue [доказано] prevMinVAlue = 2 * curMinvalue - y.

2 * curMinValue - y - это число, которое нам нужно обновить сейчас до 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; 
}

Ответ 29

Редактировать: это взято из ссылки, упомянутой в конце, как ссылка, упоминающая это вверху (PS Я не являюсь оригинальным автором этой статьи, все отзывы принадлежат автору статьи, упомянутой в ссылке) - https://www.geeksforgeeks.org/design-a-stack-that-supports-getmin-in-o1-time-and-o1-extra-space/

Мы определяем переменную minEle, которая хранит текущий минимальный элемент в стеке. Теперь интересная часть - как справиться со случаем, когда минимальный элемент удален. Чтобы справиться с этим, мы помещаем "2x - minEle" в стек вместо x, чтобы предыдущий минимальный элемент мог быть получен с использованием текущего minEle, а его значение сохранено в стеке. Ниже приведены подробные шаги и объяснение работы.

Push (x): вставляет x в верхнюю часть стека.

  • Если стек пуст, вставьте x в стек и сделайте minEle равным x.
  • Если стек не пустой, сравните x с minEle. Возникают два случая:
    • Если x больше или равно minEle, просто вставьте x.
    • Если x меньше minEle, вставьте (2 * x - minEle) в стек и сделайте minEle равным x. Например, пусть предыдущий minEle был 3. Теперь мы хотим вставить 2. Мы обновляем minEle как 2 и вставляем 2 * 2 - 3 = 1 в стек.

Pop(): удаляет элемент из верхней части стека.

  • Удалить элемент сверху. Пусть удаленный элемент будет y. Возникают два случая:
    • Если у больше или равно minEle, минимальный элемент в стеке по-прежнему minEle.
    • Если y меньше, чем minEle, минимальный элемент теперь становится (2 * minEle - y), поэтому обновите (minEle = 2 * minEle - y). Здесь мы извлекаем предыдущий минимум из текущего минимума и его значение в стеке. Например, пусть удаляемый элемент равен 1, а minEle равен 2. Мы удаляем 1 и обновляем minEle как 2 * 2 - 1 = 3.

Важные моменты:

  • Стек не содержит фактическое значение элемента, если оно пока минимально.
  • Фактический минимальный элемент всегда сохраняется в minEle

иллюстрация

Нажмите (х)

Push(x)

  • Число для вставки: 3, стек пуст, поэтому вставьте 3 в стек и minEle = 3.
  • Число для вставки: 5, стек не пуст, 5> minEle, вставьте 5 в стек и minEle = 3.
  • Число для вставки: 2, стек не пуст, 2 <minEle, вставьте (2 * 2 -3 = 1) в стек и minEle = 2.
  • Число для вставки: 1, стек не пуст, 1 <minEle, вставьте (2 * 1-2 = 0) в стек и minEle = 1.
  • Число для вставки: 1, стек не пуст, 1 = minEle, вставьте 1 в стек и minEle = 1.
  • Число для вставки: -1, стек не пуст, -1 <minEle, вставить (2 * -1 - 1 = -3) в стек и minEle = -1.

Поп()

Pop()

  • Первоначально минимальный элемент minEle в стеке равен -1.
  • Удаленное число: -3, поскольку -3 меньше минимального элемента, удаляемое исходное число - minEle, равное -1, а новый minEle = 2 * -1 - (-3) = 1
  • Удаленное число: 1, 1 == minEle, поэтому удаленное число равно 1, а minEle по-прежнему равно 1.
  • Удалено число: 0, 0 <minEle, исходное число - minEle, равное 1, и новое minEle = 2 * 1 - 0 = 2.
  • Удалено число: 1, 1 <minEle, исходное число - minEle, равное 2, и новое minEle = 2 * 2 - 1 = 3.
  • Удалено число: 5, 5> minEle, исходное число 5, а minEle еще 3

Ниже приведена реализация на Java

    // Java program to implement a stack that supports 
    // getMinimum() in O(1) time and O(1) extra space. 
    import java.util.*; 

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

    // Constructor 
    MyStack() { s = new Stack<Integer>(); } 

    // Prints minimum element of MyStack 
    void getMin() 
    { 
        // Get the minimum number in the entire stack 
        if (s.isEmpty()) 
            System.out.println("Stack is empty"); 

        // variable minEle stores the minimum element 
        // in the stack. 
        else
            System.out.println("Minimum Element in the " + 
                            " stack is: " + minEle); 
    } 

    // prints top element of MyStack 
    void peek() 
    { 
        if (s.isEmpty()) 
        { 
            System.out.println("Stack is empty "); 
            return; 
        } 

        Integer t = s.peek(); // Top element. 

        System.out.print("Top Most Element is: "); 

        // If t < minEle means minEle stores 
        // value of t. 
        if (t < minEle) 
            System.out.println(minEle); 
        else
            System.out.println(t); 
    } 

    // Removes the top element from MyStack 
    void pop() 
    { 
        if (s.isEmpty()) 
        { 
            System.out.println("Stack is empty"); 
            return; 
        } 

        System.out.print("Top Most Element Removed: "); 
        Integer t = s.pop(); 

        // Minimum will change as the minimum element 
        // of the stack is being removed. 
        if (t < minEle) 
        { 
            System.out.println(minEle); 
            minEle = 2*minEle - t; 
        } 

        else
            System.out.println(t); 
    } 

    // Insert new number into MyStack 
    void push(Integer x) 
    { 
        if (s.isEmpty()) 
        { 
            minEle = x; 
            s.push(x); 
            System.out.println("Number Inserted: " + x); 
            return; 
        } 

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

        else
            s.push(x); 

        System.out.println("Number Inserted: " + x); 
    } 
    }; 

    // Driver Code 
    public class Main 
    { 
        public static void main(String[] args) 
        { 
            MyStack s = new MyStack(); 
            s.push(3); 
            s.push(5); 
            s.getMin(); 
            s.push(2); 
            s.push(1); 
            s.getMin(); 
            s.pop(); 
            s.getMin(); 
            s.pop(); 
            s.peek(); 
        } 
    }

Как работает этот подход?

Когда вставляемый элемент меньше чем minEle, мы вставляем "2x - minEle". Важно отметить, что 2x - minEle всегда будет меньше, чем x (доказано ниже), т.е. Новый minEle, и, пока вы будете извлекать этот элемент, мы увидим, что произошло нечто необычное, так как вытесненный элемент меньше, чем minEle. Так что будем обновлять minEle.

How 2*x - minEle is less than x in push()? 
x < minEle which means x - minEle < 0

// Adding x on both sides
x - minEle + x < 0 + x 

2*x - minEle < x 

We can conclude 2*x - minEle < new minEle

При выводе, если мы находим элемент (y) меньше текущего minEle, мы находим новый minEle = 2 * minEle - y.

How previous minimum element, prevMinEle is, 2*minEle - y
in pop() is y the popped element?

 // We pushed y as 2x - prevMinEle. Here 
 // prevMinEle is minEle before y was inserted
 y = 2*x - prevMinEle  

 // Value of minEle was made equal to x
 minEle = x .

 new minEle = 2 * minEle - y 
            = 2*x - (2*x - prevMinEle)
            = prevMinEle // This is what we wanted

Ссылки: https://www.geeksforgeeks.org/design-a-stack-that-supports-getmin-in-o1-time-and-o1-extra-space/

Ответ 30

Я думаю, что только операция нажатия страдает, достаточно. Моя реализация включает стек узлов. Каждый node содержит элемент данных, а также минимум в этот момент. Этот минимум обновляется каждый раз, когда выполняется операция push.

Вот несколько моментов для понимания:

  • Я реализовал стек, используя Связанный список.

  • Верхний указатель всегда указывает на последний нажатый элемент. Если в этом стеке нет элемента, это NULL.

  • При перемещении элемента выделяется новый node, который имеет следующий указатель, указывающий на предыдущий стек и верхний, обновляется, чтобы указать на этот новый node.

Единственное отличие от обычной реализации стека заключается в том, что во время push он обновляет член min для нового node.

Пожалуйста, посмотрите код, который реализован на С++ для демонстрационной цели.

/*
 *  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.