Min Stack

Q: Jak znaleźć minimum stosu w czasie O(1)?

Zapisuj minimum w chwili dodania elementu. Stos zmienia się tylko na wierzchołku, więc minimum wartości poniżej dowolnego poziomu nie może się zmienić, gdy stos jest wypełniony do tego poziomu. Utrzymuj drugi stos z minimum na każdym poziomie albo tylko z każdym nowym minimum, a getMin będzie odczytem jego wierzchołka.

Q: Dlaczego dodawać wartość na stos minimum, gdy jest równa bieżącemu minimum?

Ponieważ minimum może znajdować się na stosie więcej niż raz. Jeśli zapisujesz tylko wartości ściśle mniejsze, dwie kopie -2 współdzielą jeden wpis w mins . Pierwsze zdjęcie -2 ze stosu usuwa ten wpis, a getMin podaje wtedy poprzednie minimum, mimo że drugie -2 nadal tam jest. Zapisywanie równych wartości daje każdej kopii własny wpis.

Q: Czy stos Min można zaimplementować z dodatkową przestrzenią O(1)?

Tak, przy użyciu jednego stosu i jednej zmiennej min . Gdy umieszczasz na stosie x poniżej bieżącego minimum, zamiast tego zapisz 2x - min i ustaw min = x ; zapisana liczba jest wtedy mniejsza niż min , co ją oznacza. Gdy oznaczona liczba zostanie zdjęta ze stosu, poprzednie minimum wynosi 2 * min - stored . Działania arytmetyczne powodują przepełnienie liczb 32-bitowych w pobliżu wartości granicznych, więc potrzebne są wartości 64-bitowe, a logika znaków łatwo prowadzi do błędów; większości osób przeprowadzających rozmowy kwalifikacyjne odpowiada wersja z dwoma stosami.

Q: Czym jest złożoność czasowa i pamięciowa stosu minimum?

Każda operacja ma złożoność O(1): push, pop, top i getMin odczytują lub zmieniają tylko wierzchołek jednego albo dwóch stosów. Złożoność pamięciowa wynosi O(n) dla n przechowywanych wartości. Przechowywanie minimum obok każdej wartości zawsze wymaga 2n miejsc; przechowywanie tylko nowych minimów wymaga od n + 1 do 2n.

ŚrednieStos

+10

Zaprojektuj stos, który oprócz standardowych operacji push, pop i top potrafi podać najmniejszą przechowywaną wartość za pomocą getMin. Każda z czterech operacji musi działać w czasie O(1).

Otrzymujesz operacje w kolejności w ops, a args[i] zawiera wartość dla operacji push i 0 dla każdej innej operacji. Wykonaj je na jednym stosie, który początkowo jest pusty, i zwróć po jednym ciągu znaków dla każdej operacji: "null" dla push i pop, a liczbę zapisaną jako tekst dla top i getMin.

Funkcja

minStackOps(ops: string-array, args: integer-array) → string-array

opsstring-array: operacje, w kolejności ich wykonywania
argsinteger-array: wartość dla każdego push, 0 dla każdej innej operacji
Zwracastring-array: jedna odpowiedź na operację, jako tekst

Ograniczenia

1 ≤ ops.length ≤ 3000
args.length == ops.length
Każde ops[i] to push, pop, top lub getMin.
-2³¹+1 ≤ args[i] ≤ 2³¹-1 dla operacji push, a args[i] == 0 dla każdej innej operacji.
pop, top i getMin są wywoływane tylko wtedy, gdy stos zawiera co najmniej jedną wartość.

Przykłady

Wejście: ops = ["push", "push", "push", "getMin", "pop", "top", "pop", "getMin"]args = [4, 1, 7, 0, 0, 0, 0, 0]
Wyjście: ["null", "null", "null", "1", "null", "1", "null", "4"]
Wyjaśnienie: Stos zawiera kolejno od dołu 4, 1 i 7, więc najmniejsza wartość to 1. Zdjęcie 7 pozostawia 1 na wierzchu. Zdjęcie również 1 pozostawia tylko 4, więc minimum wraca do 4.

Wejście: ops = ["push", "push", "push", "getMin", "pop", "getMin", "pop", "getMin"]args = [3, -2, -2, 0, 0, 0, 0, 0]
Wyjście: ["null", "null", "null", "-2", "null", "-2", "null", "3"]
Wyjaśnienie: Minimum, -2, zostaje dodane dwukrotnie. Pierwsze zdjęcie usuwa jedną kopię, a druga nadal pozostaje, więc getMin nadal zwraca -2. Dopiero po drugim zdjęciu minimum wraca do 3.

+16 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Czy potrafisz zbudować kolejkę FIFO, która dodatkowo podaje swoją minimalną wartość w zamortyzowanym czasie O(1)?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Zwykły stos obsługuje już operacje push, pop i top w czasie O(1); trudność polega na tym, by minimum przetrwało operacje usuwania. Kluczowa jest tu zasada: stos zmienia się tylko na samej górze — dopóki wartość znajduje się na danej wysokości, nic poniżej niej nie może się zmienić, więc minimum wszystkich elementów do tej wysokości pozostaje stałe. Zapisz to minimum podczas dodawania elementu, a jego usunięcie bezpłatnie przywróci poprzednie minimum. Poszczególne podejścia różnią się tym, co zapisują.

Przeszukuj stos przy każdym wywołaniu getMin

Intuicja

Użyj zwykłego stosu do operacji push, pop i top, a na getMin odpowiadaj, sprawdzając każdą przechowywaną wartość i wybierając najmniejszą. To zawsze działa, ponieważ sprawdza rzeczywistą zawartość w chwili wywołania.

Nie spełnia to wymagania O(1). Wywołanie getMin dla stosu zawierającego n wartości odczytuje je wszystkie. Test ukryty, który dodaje 1,500 wartości, wywołując getMin po każdym dodaniu, odczytuje około 1,500 × 1,500 / 2, czyli ponad milion wartości, podczas gdy pozostałe podejścia odczytują jedną wartość na wywołanie. System wykonujący 10^5 takich operacji odczytałby miliardy wartości.

Jedna buforowana wartość minimum nie rozwiązuje problemu. Zmienna przechowująca najmniejszą wartość sprawdza się przy dodawaniu, ale gdy ta wartość zostanie zdjęta ze stosu, nie można ustalić kolejnej najmniejszej bez ponownego przeszukiwania.

Algorytm

Przechowuj wartości na liście używanej jako stos.
Dla push x dopisz x; dla pop usuń ostatnią wartość; dla top odczytaj ją.
Dla getMin przejrzyj każdą przechowywaną wartość i zwróć najmniejszą.
Zapisz każdą odpowiedź jako tekst i zwróć listę.

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

    def push(self, x):
        self.values.append(x)

    def pop(self):
        self.values.pop()

    def top(self):
        return self.values[-1]

    def getMin(self):
        # Look at every stored value: O(n).
        smallest = self.values[0]
        for v in self.values:
            if v < smallest:
                smallest = v
        return smallest

def minStackOps(ops, args):
    stack = MinStack()
    result = []
    for op, arg in zip(ops, args):
        if op == "push":
            stack.push(arg)
            result.append("null")
        elif op == "pop":
            stack.pop()
            result.append("null")
        elif op == "top":
            result.append(str(stack.top()))
        else:
            result.append(str(stack.getMin()))
    return result

Przechowuj minimum obok każdej wartości

Intuicja

Gdy wartość znajduje się na wysokości i stosu, wartości pod nią nie mogą się zmienić, więc najmniejsza z dolnych i wartości pozostaje taka sama, dopóki ta wartość tam jest. Zapisz tę liczbę obok każdej wartości: na drugim stosie mins, gdzie mins[i] jest najmniejszą wartością spośród values[0..i].

Przy wstawieniu nowego elementu nowy wpis na stosie mins jest mniejszą z wartości x i wpisu znajdującego się pod nim. Przy usunięciu elementu zdejmij wierzchołek z obu stosów; wierzchołek stosu mins znów zawiera minimum pozostałych wartości. getMin odczytuje wierzchołek stosu mins.

W pierwszym przykładzie wstawienie wartości 4, 1 i 7 zapisuje minima 4, 1 i 1. Usunięcie 7 pozostawia 1 na wierzchołku stosu mins, a usunięcie 1 pozostawia 4. Każda operacja dotyczy tylko wierzchołków dwóch stosów, więc każda z nich ma złożoność O(1). Kosztem jest przechowywanie dodatkowej liczby dla każdej wartości.

Algorytm

Utrzymuj dwa stosy o tej samej wysokości: values i mins.
W przypadku push x umieść x na stosie values, a mniejszą z wartości x i szczytu stosu mins umieść na stosie mins (samo x, jeśli mins jest pusty).
W przypadku pop zdejmij element ze szczytu obu stosów.
W przypadku top odczytaj element ze szczytu stosu values; w przypadku getMin odczytaj element ze szczytu stosu mins.
Zapisz każdą odpowiedź jako tekst i zwróć listę.

class MinStack:
    def __init__(self):
        self.values = []
        self.mins = []    # mins[i] is the smallest of values[0..i]

    def push(self, x):
        self.values.append(x)
        self.mins.append(x if not self.mins else min(x, self.mins[-1]))

    def pop(self):
        self.values.pop()
        self.mins.pop()

    def top(self):
        return self.values[-1]

    def getMin(self):
        return self.mins[-1]

def minStackOps(ops, args):
    stack = MinStack()
    result = []
    for op, arg in zip(ops, args):
        if op == "push":
            stack.push(arg)
            result.append("null")
        elif op == "pop":
            stack.pop()
            result.append("null")
        elif op == "top":
            result.append(str(stack.top()))
        else:
            result.append(str(stack.getMin()))
    return result

Stos minimów, który rośnie tylko wtedy, gdy pojawia się nowe minimum

Intuicja

W drugim podejściu mins często się powtarza: wstaw 1, a potem 7, 8 i 9, a mins zawiera 1, 1, 1, 1. Powtarzający się wpis nie wnosi nic nowego. Zapisuj więc wartość w mins tylko wtedy, gdy staje się minimum, i usuwaj ją, gdy ta sama wartość opuszcza values.

Podczas wstawiania dodaj x do mins, jeśli mins jest puste lub x jest mniejsze lub równe jego wierzchołkowi. Podczas usuwania, jeśli wartość opuszczająca values jest równa wierzchołkowi mins, usuń też element z mins. Wierzchołek mins jest zawsze bieżącym minimum: każda wartość wstawiona po nim jest albo większa, albo była od niego mniejsza lub równa, więc również została zapisana i od tego czasu usunięta.

Porównanie musi być <=, a nie <. W drugim przykładzie wartość -2 jest wstawiana dwukrotnie. Przy użyciu < zapisywana jest tylko pierwsza kopia, pierwsze usunięcie usuwa ją z mins, a getMin zwraca 3, mimo że na stosie nadal znajduje się -2. Przy użyciu <= każda kopia otrzymuje własny wpis.

Wszystkie cztery operacje nadal działają w czasie O(1). Gdy wartości są dodawane od największej do najmniejszej, mins osiąga taką samą wysokość jak values; gdy minimum rzadko się zmienia, pozostaje krótki.

Algorytm

Utrzymuj stos values i stos mins.
Dla push x umieść x na stosie values. Jeśli mins jest pusty lub x jest mniejsze lub równe jego wierzchołkowi, umieść x również na stosie mins.
Dla pop zdejmij element ze stosu values. Jeśli usunięta wartość jest równa wierzchołkowi stosu mins, zdejmij element również ze stosu mins.
Dla top odczytaj wierzchołek stosu values; dla getMin odczytaj wierzchołek stosu mins.
Zapisz każdą odpowiedź jako tekst i zwróć listę.

class MinStack:
    def __init__(self):
        self.values = []
        self.mins = []    # each value that was a minimum when pushed; the top is the current minimum

    def push(self, x):
        self.values.append(x)
        # <= keeps one copy per equal minimum, so popping one leaves the others.
        if not self.mins or x <= self.mins[-1]:
            self.mins.append(x)

    def pop(self):
        if self.values.pop() == self.mins[-1]:
            self.mins.pop()

    def top(self):
        return self.values[-1]

    def getMin(self):
        return self.mins[-1]

def minStackOps(ops, args):
    stack = MinStack()
    result = []
    for op, arg in zip(ops, args):
        if op == "push":
            stack.push(arg)
            result.append("null")
        elif op == "pop":
            stack.pop()
            result.append("null")
        elif op == "top":
            result.append(str(stack.top()))
        else:
            result.append(str(stack.getMin()))
    return result

Pułapki i przypadki brzegowe

Błędy dotyczą powtórzeń minimum i tego, co usuwa operacja pop.

Zapisywanie nowego minimum tylko wtedy, gdy x jest ściśle mniejsze. Wtedy w mins brakuje drugiej kopii minimum, a usunięcie pierwszej kopii powoduje utratę minimum, mimo że druga nadal znajduje się na stosie. Wykrywa to drugi przykład.
Przechowywanie minimum w jednej zmiennej. Obsługuje dodawanie elementów, ale po usunięciu minimum zmienna zawiera nieaktualną wartość, a znalezienie kolejnej najmniejszej wartości wymaga przeszukania.
Porównywanie opakowanych liczb całkowitych przez referencję. W Javie Integer == Integer sprawdza, czy oba elementy są tym samym obiektem. Dzieje się tak w przypadku wartości od -128 do 127, które Java buforuje, ale nie w przypadku większości większych wartości, więc sprawdzanie przy usuwaniu elementu działa niepoprawnie tylko dla dużych wartości. Najpierw rozpakuj wartość do int, tak jak robi to kod w Javie.
Usuwanie elementu z mins przy każdym usunięciu elementu w trzecim podejściu. Zmniejsza się ono tylko wtedy, gdy usunięta wartość jest jego elementem na szczycie; w drugim podejściu oba stosy zawsze zmieniają się równolegle.
Zwracanie liczby przez pop. W tym formacie pop zwraca "null", tak jak push.

Najczęstsze pytania4

Jak znaleźć minimum stosu w czasie O(1)?

Zapisuj minimum w chwili dodania elementu. Stos zmienia się tylko na wierzchołku, więc minimum wartości poniżej dowolnego poziomu nie może się zmienić, gdy stos jest wypełniony do tego poziomu. Utrzymuj drugi stos z minimum na każdym poziomie albo tylko z każdym nowym minimum, a getMin będzie odczytem jego wierzchołka.

Dlaczego dodawać wartość na stos minimum, gdy jest równa bieżącemu minimum?

Ponieważ minimum może znajdować się na stosie więcej niż raz. Jeśli zapisujesz tylko wartości ściśle mniejsze, dwie kopie -2 współdzielą jeden wpis w mins. Pierwsze zdjęcie -2 ze stosu usuwa ten wpis, a getMin podaje wtedy poprzednie minimum, mimo że drugie -2 nadal tam jest. Zapisywanie równych wartości daje każdej kopii własny wpis.

Czy stos Min można zaimplementować z dodatkową przestrzenią O(1)?

Tak, przy użyciu jednego stosu i jednej zmiennej min. Gdy umieszczasz na stosie x poniżej bieżącego minimum, zamiast tego zapisz 2x - min i ustaw min = x; zapisana liczba jest wtedy mniejsza niż min, co ją oznacza. Gdy oznaczona liczba zostanie zdjęta ze stosu, poprzednie minimum wynosi 2 * min - stored. Działania arytmetyczne powodują przepełnienie liczb 32-bitowych w pobliżu wartości granicznych, więc potrzebne są wartości 64-bitowe, a logika znaków łatwo prowadzi do błędów; większości osób przeprowadzających rozmowy kwalifikacyjne odpowiada wersja z dwoma stosami.

Czym jest złożoność czasowa i pamięciowa stosu minimum?

Każda operacja ma złożoność O(1): push, pop, top i getMin odczytują lub zmieniają tylko wierzchołek jednego albo dwóch stosów. Złożoność pamięciowa wynosi O(n) dla n przechowywanych wartości. Przechowywanie minimum obok każdej wartości zawsze wymaga 2n miejsc; przechowywanie tylko nowych minimów wymaga od n + 1 do 2n.

Python

def minStackOps(ops, args):
    # Napisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

ops = ["push", "push", "push", "getMin", "pop", "top", "pop", "getMin"]
args = [4, 1, 7, 0, 0, 0, 0, 0]

Oczekiwane

["null", "null", "null", "1", "null", "1", "null", "4"]

Min Stack

Funkcja

Ograniczenia

Przykłady

Podpowiedzi

Rozwiązanie

Przeszukuj stos przy każdym wywołaniu getMin

Przechowuj minimum obok każdej wartości

Stos minimów, który rośnie tylko wtedy, gdy pojawia się nowe minimum

Pułapki i przypadki brzegowe

Najczęstsze pytania4

Podobne zadania