Finding the maximum element of a Stack

I have been solving this problem of Hackerrank recently .. https://www.hackerrank.com/challenges/maximum-element

A little bit about the problem

You have an empty sequence, and you will be given N queries. Each query is one of these three types:

1 x -Push the element x into the stack.

2 -Delete the element present at the top of the stack.

3 -Print the maximum element in the stack.

And my code is here - which passes the first 12 test cases.

import java.util.*;

public class Stackers {

    public static Stack stack;
    public static String output = "";
    
    public static void main(String[] args) {
        
        stack = new Stack<>();
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        
        for(int i = 0 ; i < n + 1; i++){
            
            String op = sc.nextLine();
            performOperation(op);            
            
        }
        
        sc.close();
        if(!output.isEmpty()){
            System.out.println(output);
            
        }
        
    }

    public static void performOperation(String op) {
        
        if (op.startsWith("1")){
            
            String remains = op.split(" ")[1];
            int rem = Integer.valueOf(remains);
            stack.push(rem);
            
        }else if(op.equalsIgnoreCase("2")){
            
            stack.pop();
            
        }else if(op.equals("3")){
            
            int max = (int) Collections.max(stack);
            output += (max + "\n");
            
        }
        
    }

}

But fails with "timeout" from the 13th test case. Most of the times, logic will be wrong, so I ran the 13th test case locally in my computer . I got the output in 1.3- 1.6 minutes tho:)

How can I improve my code. Please guide me or if it is the wrong stack exchange community, please advise me.

This type of question actually requires a little thinking outside the box.

The idea here, since we need to store the max with each element, is to use the built-in Stack more creatively.

public class ChallengeValue {
    public int max;
    public int value;
}

I think that should tell you where we're going:

import java.util.*;

public class Stackers {
    public static Stack stack;
    public static String output = "";

    public static void main(String[] args) {
        stack = new Stack<>();
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        for(int i = 0 ; i  newVal.value ? last.max : newVal.max;
            stack.push(newVal);
        } else if(op.equalsIgnoreCase("2")) {
            stack.pop();
        } else if(op.equals("3")) {
            int max = stack.peek().max;
            output += (max + "\n");
        }
    }
}

Now we are storing the max with the stack values, so when we pop one we get the new max immediately. This turns the max (3) command into an \$O(1)\$ operation. (Your version is likely \$O(n)\$.)

StackExchange Code Review Q#157233, answer score: 10