İçeriğe geç

Sabit zamanlı min stack

Kolay#stack#auxiliary-stack~20 dk

Görev tanımı

Problem

Bir değer push etmeyi, tepedeki değeri pop etmeyi, tepedeki değeri okumayı ve o an saklanan en küçük değeri bildirmeyi destekleyen bir stack tasarla. Bu işlemlerin her biri sabit zamanda çalışmalı; yani minimumu bulmak için içeriği taramak kabul edilmez. Minimumun yalnız stack boş değilken istendiğini varsayabilirsin.

Örnekler

Operations: push 5, push 2, push 7
minimum -> 2, top -> 7
Operations: pop, pop        (starting from the stack above)
minimum -> 5, top -> 5
Neden: 2'yi pop etmek önceki minimumu geri getirmeli
Operations: push 3, push 3, pop
minimum -> 3
Neden: edge case: tekrar eden minimumlar bir pop'tan sağ çıkmalı

İpuçları

0 / 3

Hedef zaman
O(1)
Hedef alan
O(n)

Kısıtlar

  • every operation runs in O(1) time
  • minimum is only requested on a non-empty stack

Kodda değil de fikirde mi takıldın? Min stack bunu anlatıyor.

Python 3Ctrl+Enter çalıştırır