Leetcode 155 Min Stack

Soru

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

MinStack() initializes the stack object. void push(int val) pushes the element val onto the stack. void pop() removes the element on the top of the stack. int top() gets the top element of the stack. int getMin() retrieves the minimum element in the stack.

Örnek 1

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

Çözüm

• Belirli işlemleri destekleyen özel bir yığın (stack) tasarımını gerçekleştirmenizi ister. Bu yığın, normal yığın işlevlerinin yanı sıra, yığındaki en küçük elemanı sabit zaman içinde geri döndürebilmelidir.
• Min Stack probleminin çözümü, yığın veri yapısı kullanarak yapılır. Ancak, yığının minimum değerini sabit zaman içinde alabilmek için, her elemanın yığınına eklenme anında o ana kadar olan minimum değerle birlikte eklenmesi gerekir. Böylece, yığın elemanları çıkarıldığında bile minimum değer hızlıca elde edilebilir.
• Çalışma Mekanizması:
• İnitialize: İki yığın kullanılır: stack normal yığın işlemleri için, min_stack ise şu ana kadar görülen minimum değerleri tutar.
• Push İşlemi: Yeni bir eleman eklenirken, bu eleman stacke eklenir. Eğer min_stack boşsa veya eklenen eleman min_stackin en üstündeki elemandan küçük veya eşitse, bu eleman ayrıca min_stacke de eklenir.
• Pop İşlemi: Eleman çıkarılırken, stackten eleman çıkarılır. Eğer bu eleman min_stackin en üstündeki elemana eşitse, min_stackten de çıkarılır.
• Top İşlemi: stackin en üstündeki eleman döndürülür.
• GetMin İşlemi: min_stackin en üstündeki eleman, yığının şu ana kadar gördüğü minimum değerdir ve bu değer döndürülür.

Code

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, x):
        # Elemanı normal yığınına ekle
        self.stack.append(x)
        # Min yığınına şu ana kadar olan en küçük elemanı ekle
        if not self.min_stack or x <= self.min_stack[-1]:
            self.min_stack.append(x)

    def pop(self):
        # Elemanı normal yığınından çıkar
        popped = self.stack.pop()
        # Eğer çıkarılan eleman min yığınının en üstündeyse, min yığınından da çıkar
        if self.min_stack and popped == self.min_stack[-1]:
            self.min_stack.pop()

    def top(self):
        # En üstteki elemanı döndür
        return self.stack[-1]

    def getMin(self):
        # Min yığınının en üstündeki elemanı döndür
        return self.min_stack[-1]

Complexity

• Time complexity (Zaman Karmaşıklığı) : Tüm işlemler O(1) zaman karmaşıklığına sahiptir.
• Space complexity (Alan Karmaşıklığı) : O(n), burada n yığına eklenen eleman sayısıdır. İki yığın kullanıldığı için, ekstra alan gereksinimi vardır.