спроектировать стек таким образом, чтобы getMinimum () был равен O (1)

Question

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

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

Answer 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

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

(Недостатком, конечно, является то, что он удваивает требования к пространству. Время выполнения не сильно страдает, хотя - то есть это все та же сложность.)

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

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

Answer 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.;

Однако ни один из них не является истинно О (1). На практике им не требуется больше места, потому что они используют дыры в представлениях чисел, объектов или указателей на этих языках. Но теоретическая машина, которая использовала более компактное представление, потребовала бы добавления дополнительного бита к этому представлению в каждом случае.

Answer 4

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

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

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

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

Answer 5

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

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

Answer 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

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

Answer 8

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

}

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

Answer 10

Я публикую полный код здесь, чтобы найти минимальное и максимальное значения в данном стеке.

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

Дайте мне знать, если у вас возникли проблемы

Спасибо, Викаш