Min Stack

Q: Bagaimana cara mendapatkan nilai minimum dari stack dalam waktu O(1)?

Simpan stack kedua di samping nilai yang mencatat nilai minimum pada setiap tingkat, atau hanya setiap nilai minimum baru. getMin kemudian membaca nilai teratasnya, dan setiap operasi push dan pop memperbarui kedua stack dalam O(1).

Q: Bisakah Min Stack dibuat dengan ruang ekstra O(1)?

Ya, dengan satu stack dan variabel min . Untuk memasukkan x di bawah min , simpan 2x - min , yang lebih kecil daripada x dan menandai entri tersebut, lalu tetapkan min = x . Saat mengeluarkan entri bertanda s , pulihkan nilai minimum sebelumnya dengan 2 * min - s . Di dekat batas 32-bit, cara ini memerlukan nilai 64-bit.

Q: Berapa kompleksitas waktu dan ruang dari Min Stack?

Setiap operasi memiliki kompleksitas O(1): push, pop, top, dan getMin masing-masing hanya membaca atau mengubah bagian teratas dari satu atau dua stack. Ruang yang digunakan adalah O(n) untuk n nilai yang disimpan. Menyimpan nilai minimum di samping setiap nilai selalu menggunakan 2n slot; menyimpan hanya nilai minimum baru menggunakan antara n + 1 dan 2n slot.

SedangStack

+10

Rancang sebuah stack yang, selain operasi umum push, pop, dan top, dapat melaporkan nilai terkecil yang disimpannya dengan getMin. Keempat operasi harus berjalan dalam waktu O(1).

Kamu mendapatkan operasi secara berurutan dalam ops, dengan args[i] menyimpan nilai untuk operasi push dan 0 untuk setiap operasi lainnya. Jalankan operasi tersebut pada satu stack yang awalnya kosong, lalu kembalikan satu string untuk setiap operasi: "null" untuk push dan pop, serta angka dalam bentuk teks untuk top dan getMin.

Fungsi

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

opsstring-array: operasi-operasi, sesuai urutan dijalankannya
argsinteger-array: nilai untuk setiap push, 0 untuk setiap operasi lainnya
Mengembalikanstring-array: satu jawaban untuk setiap operasi, sebagai teks

Batasan

1 ≤ ops.length ≤ 3000
args.length == ops.length
Setiap ops[i] adalah push, pop, top, atau getMin.
-2³¹+1 ≤ args[i] ≤ 2³¹-1 untuk operasi push, dan args[i] == 0 untuk operasi lainnya.
pop, top, dan getMin hanya dipanggil saat stack menyimpan setidaknya satu nilai.

Contoh

Input: ops = ["push", "push", "push", "getMin", "pop", "top", "pop", "getMin"]args = [4, 1, 7, 0, 0, 0, 0, 0]
Output: ["null", "null", "null", "1", "null", "1", "null", "4"]
Penjelasan: Stack menyimpan 4, 1, dan 7 dari bawah ke atas, jadi nilai terkecilnya adalah 1. Mengeluarkan 7 menyisakan 1 di bagian atas. Mengeluarkan 1 juga hanya menyisakan 4, sehingga nilai minimum kembali menjadi 4.

Input: ops = ["push", "push", "push", "getMin", "pop", "getMin", "pop", "getMin"]args = [3, -2, -2, 0, 0, 0, 0, 0]
Output: ["null", "null", "null", "-2", "null", "-2", "null", "3"]
Penjelasan: Nilai minimum, -2, di-push dua kali. Pop pertama menghapus satu salinan dan salinan lainnya masih ada, jadi getMin tetap -2. Nilai minimum baru kembali menjadi 3 setelah pop kedua.

Pertanyaan lanjutan

Bisakah kamu membuat queue first in, first out yang juga melaporkan nilai minimumnya dalam waktu amortisasi O(1)?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Stack biasa sudah menjalankan push, pop, dan top dalam O(1). Stack hanya berubah di bagian atasnya, jadi selama suatu nilai berada pada ketinggian tertentu, nilai minimum dari semua nilai hingga ketinggian itu tetap. Catat nilai minimum itu saat melakukan push, dan pop akan memulihkan nilai sebelumnya tanpa biaya tambahan.

Pindai tumpukan setiap kali memanggil getMin

Intuisi

Jawab getMin dengan memindai setiap nilai yang tersimpan. Cara ini selalu tepat karena membaca isi yang sebenarnya, tetapi pemanggilan getMin pada n nilai akan membaca semua n nilai. Dengan 1.500 operasi push, yang masing-masing diikuti pemanggilan getMin, jumlahnya lebih dari satu juta pembacaan, sementara pendekatan lain hanya membaca satu nilai per pemanggilan.

Menyimpan satu nilai minimum dalam cache tidak menyelesaikan masalah. Setelah nilai itu dikeluarkan, kamu perlu memindai lagi untuk menemukan nilai terkecil berikutnya.

Algoritma

Simpan nilai-nilai dalam list yang digunakan sebagai stack.
Untuk push x, tambahkan x; untuk pop, hapus nilai terakhir; untuk top, baca nilainya.
Untuk getMin, telusuri setiap nilai yang tersimpan dan kembalikan nilai terkecil.
Catat setiap jawaban sebagai teks dan kembalikan list tersebut.

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

Simpan nilai minimum di samping setiap nilai

Intuisi

Simpan stack kedua mins, dengan mins[i] sebagai nilai terkecil dari values[0..i]. Operasi push menyimpan nilai yang lebih kecil antara x dan entri di bawahnya. Operasi pop menghapus elemen teratas dari kedua stack, dan elemen teratas mins kembali menjadi nilai minimum dari elemen yang tersisa. Pada contoh pertama, operasi push untuk 4, 1, dan 7 menyimpan nilai minimum 4, 1, dan 1; operasi pop untuk 7 lalu 1 menyisakan 4.

Setiap operasi hanya menyentuh elemen teratas dari dua stack, jadi masing-masing berbiaya O(1). Kekurangannya, diperlukan satu angka tambahan untuk setiap nilai.

Algoritma

Pertahankan dua stack dengan tinggi yang sama, values dan mins.
Untuk push x, masukkan x ke values, lalu masukkan nilai yang lebih kecil antara x dan elemen teratasnya ke mins (x jika mins kosong).
Untuk pop, keluarkan elemen dari kedua stack.
Untuk top, baca elemen teratas values; untuk getMin, baca elemen teratas mins.
Catat setiap jawaban sebagai teks dan kembalikan list tersebut.

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

Stack nilai minimum yang hanya bertambah saat ada nilai minimum baru

Intuisi

Pada pendekatan kedua, mins sering mengulang nilai yang sama: masukkan 1, 7, 8, dan 9, lalu isinya menjadi 1, 1, 1, 1. Jadi, catat nilai di mins hanya saat nilai itu menjadi nilai minimum, yaitu ketika mins kosong atau x kurang dari atau sama dengan elemen teratasnya, dan keluarkan elemen dari mins saat nilai yang sama dikeluarkan dari values.

Elemen teratas mins tetap menjadi nilai minimum: nilai apa pun yang dimasukkan setelahnya pasti lebih besar, atau kurang dari atau sama dengannya dan dicatat di mins, yang berarti nilai itu sudah dikeluarkan sejak saat itu. Gunakan <= agar setiap salinan nilai minimum memiliki entrinya sendiri. Keempat operasi tetap O(1), dan mins hanya akan setinggi values jika nilai-nilai masuk dari yang terbesar hingga yang terkecil.

Algoritma

Simpan stack values dan stack mins.
Untuk push x, dorong x ke values. Jika mins kosong atau x paling banyak sama dengan elemen teratasnya, dorong x ke mins juga.
Untuk pop, keluarkan elemen dari values. Jika nilai yang dikeluarkan sama dengan elemen teratas mins, keluarkan elemen dari mins juga.
Untuk top, baca elemen teratas values; untuk getMin, baca elemen teratas mins.
Catat setiap jawaban sebagai teks dan kembalikan list-nya.

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

Jebakan dan kasus tepi

Mencatat nilai minimum baru hanya ketika x lebih kecil secara ketat. Dalam contoh kedua, kedua salinan -2 berbagi satu entri di mins, pop pertama menghapusnya, lalu getMin mengembalikan 3 sementara -2 masih ada di stack.
Melakukan pop pada mins setiap kali melakukan pop dalam pendekatan ketiga. Ukurannya hanya berkurang ketika nilai yang dihapus sama dengan nilai teratasnya.
Membandingkan integer yang dibungkus di Java dengan Integer == Integer. Ini memeriksa identitas object, yang berlaku untuk nilai cache -128 sampai 127 dan gagal untuk sebagian besar nilai yang lebih besar. Lakukan unboxing ke int terlebih dahulu.
Mengembalikan angka untuk pop. Dalam format ini, pop mengembalikan "null", sama seperti push.

Pertanyaan yang sering diajukan3

Bagaimana cara mendapatkan nilai minimum dari stack dalam waktu O(1)?

Simpan stack kedua di samping nilai yang mencatat nilai minimum pada setiap tingkat, atau hanya setiap nilai minimum baru. getMin kemudian membaca nilai teratasnya, dan setiap operasi push dan pop memperbarui kedua stack dalam O(1).

Bisakah Min Stack dibuat dengan ruang ekstra O(1)?

Ya, dengan satu stack dan variabel min. Untuk memasukkan x di bawah min, simpan 2x - min, yang lebih kecil daripada x dan menandai entri tersebut, lalu tetapkan min = x. Saat mengeluarkan entri bertanda s, pulihkan nilai minimum sebelumnya dengan 2 * min - s. Di dekat batas 32-bit, cara ini memerlukan nilai 64-bit.

Berapa kompleksitas waktu dan ruang dari Min Stack?

Setiap operasi memiliki kompleksitas O(1): push, pop, top, dan getMin masing-masing hanya membaca atau mengubah bagian teratas dari satu atau dua stack. Ruang yang digunakan adalah O(n) untuk n nilai yang disimpan. Menyimpan nilai minimum di samping setiap nilai selalu menggunakan 2n slot; menyimpan hanya nilai minimum baru menggunakan antara n + 1 dan 2n slot.

def minStackOps(ops, args):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

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

Output yang diharapkan

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

Min Stack

Fungsi

Batasan

Contoh

Petunjuk

Solusi

Pindai tumpukan setiap kali memanggil getMin

Simpan nilai minimum di samping setiap nilai

Stack nilai minimum yang hanya bertambah saat ada nilai minimum baru

Jebakan dan kasus tepi

Pertanyaan yang sering diajukan3

Soal serupa