Min Stack Leetcode решение  


Ниво на трудност Лесно
Често задавани в Амазонка ябълка Bloomberg Capital One Microsoft Оракул
алгоритми кодиране Дизайн Интервю интерпретация LeetCode LeetCodeSolutions Стек

Декларация за проблема  

Дизайн a купчина който поддържа push, pop, top и извличане на минималния елемент за постоянно време.

push (x) - Натиснете елемент x върху стека.
pop () - Премахва елемента в горната част на стека.
top () - Вземете най-горния елемент.
getMin () - Извлича минималния елемент в стека.

Забележка: Методите pop, top и getMin операциите винаги ще бъдат извиквани на непразни стекове.

Пример

push(-2);
push(0);
push(-3);
getMin();
pop();
top();
getMin();
-3
0
-2

Обяснение:

MinStack minStack = нов MinStack ();
minStack.push (-2);
minStack.push (0);
minStack.push (-3);
minStack.getMin (); // връщане -3
minStack.pop ();
minStack.top (); // връщане 0
minStack.getMin (); // връщане -2

Подход  

Знаем, че стекът е структура от данни, в която можем лесно да натиснем елемент в края и също така лесно да осъществим достъп или да пуснем последния вмъкнат елемент. Тези операции се случват за O (1) време в стека. Но в този проблем трябва да направим допълнителна функция getMin, която трябва да може да извлече минималния елемент в стека и това също за O (1) време.

Така че, за да проектираме тази структура от данни, очевидно ще използваме стека като основна структура от данни, но трябва да добавим допълнителен алгоритъм към нея, за да можем да получим минимален елемент за постоянно време.

За това нека видим пример. Да предположим, че трябва да вмъкнем тези елементи в стека по ред:
5 6 4 7 5 3 и след това започнете да пукате.

Вижте също
Комбинации Leetcode Solution

Min Stack Leetcode решениещифт

Можем да забележим, че когато извадим елемента, който също е текущ минимум, новият минимум е същият, както беше преди да го натиснем. Така че трябва да знаем всички предишни минимални елементи досега, за да можем да извлечем минимума след премахване на текущия минимален елемент за O (1) време.

За това можем да използваме друг стек, който ще съхранява само минималния елемент (представен със зелен цвят на фиг.) От основния стек. Така че горният елемент на минималния стек ще покаже текущия минимален елемент.

По време на вмъкване или премахване на елемент ще актуализираме минния стек, както е показано по-долу:

  • Ако новият изтласкан елемент е по-малък или равен на текущия минимум, тогава ние натискаме този елемент в min stack също за актуализиране на текущия минимум.
  • Ако изскачащият елемент е равен на текущия минимум, тогава премахваме този елемент от минния стек също, за да актуализираме текущия минимум.

изпълнение  

C ++ програма за Min Stack Leetcode Solution

#include <bits/stdc++.h>
using namespace std;

class MinStack {
public:
    stack<int> st,mn;
    
    void push(int x) 
    {
        if(st.empty() || x<=mn.top())
            mn.push(x);
        st.push(x);
    }
    
    void pop() 
    {
        if(st.top()==mn.top()) 
            mn.pop();
        st.pop();
    }
    
    int top() 
    {
        return st.top();
    }
    
    int getMin() 
    {
        return mn.top();
    }
};

int main() 
{
    MinStack* minStack = new MinStack();
    minStack->push(-2);
    minStack->push(0);
    minStack->push(-3);
    int param1 = minStack->getMin(); 
    minStack->pop();
    int param2 = minStack->top();   
    int param3 = minStack->getMin(); 
    
    cout<<param1<<endl;
    cout<<param2<<endl;
    cout<<param3<<endl;
    
    return 0; 
}
-3
0
-2

Java програма за Min Stack Leetcode Solution

import java.util.*;
class MinStack {

    Stack<Integer> st=new Stack<>();
    Stack<Integer> mn=new Stack<>();
   
    public void push(int x) 
    {
        if(st.empty() || x<=mn.peek())
            mn.push(x);
        st.push(x);
    }
    
    public void pop() 
    {
        if(st.peek().equals(mn.peek())) 
            mn.pop();
        st.pop();
    }
    
    public int top() 
    {
         return st.peek();
    }
    
    public int getMin() 
    {
        return mn.peek();
    }
}

class Rextester{

  public static void main(String args[])
    {
        MinStack minStack = new MinStack();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        int param1 = minStack.getMin(); 
        minStack.pop();
        int param2 = minStack.top();   
        int param3 = minStack.getMin(); 
        
    System.out.println(param1);
        System.out.println(param2);
        System.out.println(param3);
    }
}
-3
0
-2

Анализ на сложността за решение с минимален стек Leetcode  

Сложност във времето

O (1): O (1) за всички операции. Както знаем, стекът отнема постоянно време за push, pop и top. За getMin използвахме друг стек, който кара тази функция да работи и в постоянно време.

Вижте също
Намерете k-тия най-малък елемент в BST (Статистика за поръчките в BST)

Сложност на пространството 

На) : В най-лошия случай цялата операция е push, следователно сложността на пространството е O (n).

1