Основы, проблемы структуры данных, максимальное количество в стеке

Question

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

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

• добавьте число X в стопку, когда я наберу 1
• , удалите верхнюю часть стопки с помощью 2
• и напечатайте максимальное число в стопке с помощью 3

таким образом

Это должно быть решено с массивами, массивами, стеками, очередями или деревьями.Это то, что я сделал, но оно превышает 6,51 с:

import java.util.*;

class Main {

public static void maxStack(int a, int val, Stack stack) {

    switch (a) {
        case 1:
            stack.add(val);
            break;
        case 2:
            if (stack.isEmpty()) {
                break;
            }
            int c = (int) stack.pop();
            break;
        case 3:

            Object o[] = stack.toArray();
            Arrays.sort(o);
            System.out.println(o[o.length - 1]);
            break;
        default:
            break;
    }
}

public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);

    Stack<Integer> stack = new Stack<Integer>();

    int val = 0;

    int a = scan.nextInt();
    while (a-- > 0) {
        int t = scan.nextInt();
        if (t == 1) {
            val = scan.nextInt();
        }
        maxStack(t, val, stack);
    }
    scan.close();
}
}

Любая рекомендация?

Answer 1

Вы превышаете время, потому что каждый раз, когда вы выполняете операцию sort над ними.Эта проблема может быть решена двумя способами

1. с использованием времени O (1) и пространства O (n) с использованием вспомогательного стека
2. с использованием времени O (1) и O (1)пробел

вставка, удаление, макс. в O (1)