Bu röportaj bir soru. Bir yığın tasarım için gereken getMinimum böyle bir tamsayı değeri tutan() işlevi, minimum eleman yığın dönmelidir.

Örneğin: aşağıdaki örnek düşünün

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 en küçük değeri(1) dönmelidir
2. Alan kısıtlaması da tasarlarken dikkate alınması ve eğer fazladan bir boşluk kullanırsanız, sürekli bir boşluk olmalı.

EDİT: Bu "sabit alan" kısıtlama - bu temelde gerekli alanı iki katına çıkar. Ben bir çözüm olduğunu hiç sanmıyorumyoko halde, bir yerde çalışma zamanı karmaşıklığı (örn yapma push/pop O(n)) bozmadan. Bu değişmez unutmayınkarmaşıklığıalan gerekli ise O yığın(n) uzay gereksinimleri varsa, örneğin, bu hala O(n) sadece farklı sabit bir faktör olacaktır.

Sabit olmayan-çözüm alanı

Bir "" yığın "en az alt yığın değerleri". tutuyorsunuz Ana yığını pop, dk da bir yığın pop. Ana yığın bastığınızda, iki yeni unsur ya da hangisi daha düşük akım min, itin. getMinimum() minStack.peek() olarak uygulanır.

Bu yüzden örnek olarak kullanarak, olurdu:

Real stack        Min stack

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

İki kez patlama sonra:

Real stack        Min stack

4                 2
6                 2
2                 2

Bana eğer bu Bilgi yeterli değil eğer doğru değilse lütfen bize bildirin. Sen grok zaman basit ama kafa karıştırıcı ilk başta biraz zaman alır :)

(Tabii olumsuz alanı gereksinimi iki katına çıkar. Yürütme zamanı önemli ölçüde rağmen hala aynı şey - yani karmaşıklık zarar görmüyor.)

EDİT: biraz daha keman, ama genel olarak daha iyi bir yer olan bir değişim Var. Biz hala min yığını var, ama biz sadece ana yığından biz pop değeri min yığında eşit olduğunda pop. Biz sadeceitinbu değer ana yığını üzerine itiliyor, daha az min yığınıya da eşitmin akım değeri. Bu min yinelenen değerlere izin verir. getMinimum() hala sadece göz operasyonu. Örneğin, orijinal versiyonunu alıp tekrar 1 bastırıyor, alırdık:

Real stack        Min stack

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

Yukarıda haşhaş 1 == 1, gidiyor çünkü her iki yığınları ortaya:

Real stack        Min stack

5  --> TOP        1
1                 2
4                 
6                 
2

Yine modasadeceana yığından pop, 5 ^ çünkü . 1:

Real stack        Min stack

1                 1
4                 2
6                 
2

Yine haşhaş 1 == 1 çünkü her iki yığınları babalık:

Real stack        Min stack

4                 2
6                 
2

Bu eğer biz nadiren eğer aynı kötü durum uzay karmaşıklığı (çift orijinal yığın) ama çok daha iyi alan kullanımı ile biter "yeni en küçük veya eşit".

EDİT: Burada Pete'in kötü düzeni uygulaması. İyice, ama ben denemedimdüşünüyorumsorun değil :)

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