1

スタックからポップするたびに、スタック内の最小要素がわかるように、スタックをどのように維持しますか? アルゴリズムは一定の複雑さを持つ必要があります

前もって感謝します

4

3 に答える 3

3

わかりました、これがあなたがする必要があることです..

data structure挿入する各要素の含まれている情報、その要素を挿入したときの値は何かを維持する必要がありminimumます。second minimum

したがって、次のような情報が必要です。

押された要素ごとに ->

  • 挿入後の最小値
  • 挿入前の最小値

この情報は、その要素をスタックから取得するときに必要になります。したがって、最小値popであるかどうかがわかります。そうであれば、この要素をプッシュする前に現在の値を に置き換えることができます。そうでない場合は、その時点での価値の変化はありません..poppingminimumminimum valueminimum

例: -

現在、スタックに次の要素があるとします: -

[3, 5, 7, 9, 2, 4]

  • そして、値 8をプッシュします..次に、維持する値が 2 つあります..(8 がプッシュされる前の最小値、つまり 2、および 8 が挿入された後の最小値、つまり 2): -

    min_value_before_push = min(stack)
push 8
min_value_after_push = min(stack)

  • 値 1をプッシュすると、minimum_before_insertion2 になり、minimum_after_insertion1 になります。

    min_value_before_push = 2
min_value_after_push = 1

今あなたのスタックは:-

[1, 8, 3, 5, 7, 9, 2, 4]

今、あなたならpop、あなたはそれを見るでしょうvalue 1： -

    min_value_before_push = 2
    min_value_after_push = 1

したがって、ポップすると最小値が変更されます。したがって、現在の最小値をminimum_value_before_push1.. で変更します。したがって、最小値は 2..

現在のスタックは : -

[8, 3, 5, 7, 9, 2, 4]

それでは、このアルゴリズムが要素に対して機能するかどうかを確認しましょうduplicate: -

もう一度押したいとvalue 2します..

min_value_before_push = 2
min_value_after_push = 2

次に進むと、popfor が 2 であることがわかります。これは、ポップすると最小値が変更されることを意味します。したがって、この値を に置き換えます。これも 2 です。value 2min_value_after_pushmin_value_before_push

注: - このアルゴリズムの利点の 1 つは、多くの比較を行う必要がないことcurrent_minimum_valueです。current_minimum_valuepop

あなたは何ができるかを考え続けることdata structureができます..

于 2012-09-28T06:26:01.533 に答える
2

免責事項: null 値は禁止されており (ArrayDeque と同様)、厳密にテストされていません。 

import java.util.ArrayDeque;

public class PessimisticStack<T extends Comparable<? super T>> {

    private class Entry {
        private Entry(T t, T minNow) {
            this.t = t;
            this.minNow = minNow;
        }
        private final T t;
        private final T minNow;
    }

    private final ArrayDeque<Entry> deque;

    public PessimisticStack() {
        deque = new ArrayDeque<Entry>();
    }

    public PessimisticStack(int initialCapacity) {
        deque = new ArrayDeque<Entry>(initialCapacity);
    }

    public void push(T t) {
        if (t == null) throw new NullPointerException();
        Entry entry = null; 
        if (deque.isEmpty()) {
            entry = new Entry(t, t);
        }
        else {
            T prevMinimum = deque.peek().minNow;
            T newMinimum = null;
            if (t.compareTo(prevMinimum) < 0) {
                newMinimum = t;
            }
            else {
                newMinimum = prevMinimum;
            }
            entry = new Entry(t, newMinimum);
        }
        deque.push(entry);
    }

    public T pop() {
        return deque.pop().t;
    }

    public T getMinimum() {
        Entry entry = deque.peek();
        return (entry == null ? null : entry.minNow);
    }
}

使用例

PessimisticStack<String> stack = new PessimisticStack<String>();

stack.push("Zebra");
stack.push("Elephant");
stack.push("Bryan");
stack.push("Adam");
stack.push("Calvin");

String calvin = stack.pop();

// "Adam"
System.err.println(stack.getMinimum());

stack.push("Aaron");

// "Aaron"
System.err.println(stack.getMinimum());

String aaron = stack.pop();

// "Adam"
System.err.println(stack.getMinimum());

String adam = stack.pop();

// "Bryan"
System.err.println(stack.getMinimum());
于 2012-09-28T07:12:06.110 に答える
1

minStackたとえば、要素をプッシュするときに別のスタックを使用し、プッシュする場合はプッシュvalするかどうかを確認します。から pop するときは、値 pop を確認します。val < minStack.peek()valminStackstackpop_valminStack.pop()pop_val == minStack.peek()

特定の時点 (minStack への次のプッシュが行われるまで) をすべて保持する ができたので、スタックのトップが であるかどうかを確認するだけで、いつ minStack からポップするかを簡単に判断できminStackます。すでに上で紹介しました。local-min-elementlocal-min-element

ただし、このメソッドは、すべての要素が互いに一意である場合にのみ適切に機能します。それ以外の場合は、カウンターを使用すること、ヒント、使用することが少し難しくなります:)。

于 2012-09-28T06:38:39.760 に答える