Поиск минимального значения из стека

Question

Я пытаюсь решить этот вопрос с помощью Stack из LeetCode, я могу пройти только тесты 14/18 тестов, поскольку тесты недоступны. Я не могу понять, какие крайние случаи отсутствуют. Я новичок в Java, так оцененная помощь :-)

  public class MinStack { 

       private int top; 
       private ArrayList<Integer> stack; 
       private ArrayList<Integer> minStack; 

       /** initialize your data structure here. */ 
       public MinStack() { 
        this.top = -1; 
        this.stack = new ArrayList<Integer>(); 
        this.minStack = new ArrayList<Integer>(); 
       } 

       public void push(int x) { 
        top++; 
        stack.add(x); 
        if(top == 0){ 
         minStack.add(x); 
        } 
        else{ 
         minStack.add(Math.min(minStack.get(top-1), x)); 

        } 
       } 

       public void pop() { 
        stack.remove(stack.get(top)); 
        minStack.remove(minStack.get(top)); 
        top--; 
       } 

       public int top() { 
        if(top >= 0) 
         return stack.get(top); 
        return -1; 
       } 

       public int getMin() { 
        if(top >= 0) 
         return minStack.get(top); 
        return -1; 
       } 
      } 

      /** 
      * Your MinStack object will be instantiated and called as such: 
      * MinStack obj = new MinStack(); 
      * obj.push(x); 
      * obj.pop(); 
      * int param_3 = obj.top(); 
      * int param_4 = obj.getMin(); 
      */ 

Answer 1

1. Вы можете использовать Stack<Integer> для стека и length свойство для вершины стека.

2. stack.remove(Object o) удаляет первое вхождение объекта в структуру данных резервного копирования, ArrayList в вашем случае. Если вы используете Stack<Integer>, просто позвоните stack.pop(). Или вызовите stack.remove(top), если используете ArrayList.

Алгоритм выглядит хорошо для меня.

Answer 2

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

Рассмотрим стек поп операций 1,7,3,4 , 2, 8,9. Несомненно, 1 на вершине этого стека является минимальным. Но если вызывается pop, 1 удаляется ... Из-за отсутствия правильной сортировки нет гарантии, что следующий элемент в верхней части стека будет минимальным.

в этой линии

minStack.add (Math.min (minStack.get (топ-1), х));

и пример выше, 1 всегда добавляется в стек, являясь минимальным. Таким образом, когда 1 выскочит, 1 по-прежнему является минимальным в вашем minStack, но должен быть 2 из приведенного выше примера