Time limit exceeded in maximum value of stack(TLE error)

Question

I am given a question on stacks ds : You have been given a sequence A of N digits. Each digit in this sequence ranges from 1 to 10^9. You need to perform 2 types of operations on this list:

Add(x): Add element x to the end of the list. Max(list): Find the maximum element in the current sequence. For each query of type 2, you need to print the result of that operation.

Sample Input
5
1 2 3 4 5
6
1 1
1 2
1 3
2
1 8
2

Sample Output
5
8

code:

import java.util.*;
public class Main {
    public static void main(String args[])
    {
        Stack<Integer> stack = new Stack<Integer>();
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        for(int i=0;i<n;i++){
            stack.add(sc.nextInt());
        }
        
        int a=sc.nextInt();
        for (int j=0;j<a;j++){
            int x=sc.nextInt();
            if (x==1){
                int y=sc.nextInt();
                stack.add(y);
            }
            else{
            System.out.println(Collections.max(stack));      
        }
            }
        }
    }

I am just failing this one test case, that too because of the time limit exceeding, could someone suggest some methods to reduce the time taken?

Answer 1

Collections.max(stack) takes O(n) every time when it is being called, it iterates every element in the stack and finds the max

Why don't you store the max in a local variable and compare with it every time when adding a new value to Stack?

public static void main(String[] args) {
    Stack<Integer> stack = new Stack<Integer>();
    int max = Integer.MIN_VALUE;
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    for (int i = 0; i < n; i++) {
        int value = sc.nextInt();
        stack.add(value);
        max = Math.max(max, value);
    }

    int a = sc.nextInt();
    for (int j = 0; j < a; j++) {
        int x = sc.nextInt();
        if (x == 1) {
            int y = sc.nextInt();
            stack.add(y);
            max = Math.max(max, y);
        } else {
            System.out.println(max);
        }
    }
}