Решение Leetcode с минимальным стеком


Сложный уровень Легко
Часто спрашивают в Амазонка Apple Bloomberg Capital One Microsoft Oracle
Дизайн Стек

Постановка задачи

Проектирование стек который поддерживает 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 с минимальным стеком

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

Для этого мы можем использовать другой стек, который будет хранить только минимальный элемент (обозначенный зеленым цветом на рис.) Основного стека. Таким образом, верхний элемент минимального стека будет указывать текущий минимальный элемент.

Во время вставки или удаления элемента мы обновим минимальный стек, как показано ниже:

  • Если новый толкаемый элемент меньше или равен текущему минимуму, мы помещаем этот элемент в минимальный стек, чтобы обновить текущий минимум.
  • Если всплывающий элемент равен текущему минимуму, тогда мы удаляем этот элемент из минимального стека, чтобы обновить текущий минимум.

Реализация

Программа C ++ для решения Min Stack Leetcode

#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

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 с минимальным стеком

Сложность времени

О (1): O (1) для всех операций. Как мы знаем, stack занимает постоянное время для push, pop и top. Для getMin мы использовали другой стек, который заставляет эту функцию также работать с постоянным временем.

Космическая сложность 

На) : В худшем случае все операции выполняются принудительно, следовательно, сложность пространства равна O (n).