Java solution 420ms without Stack.class , Anybody know <400ms in java?


  • 0
    A
        List<Integer> stack = new ArrayList<Integer>();
        Integer min = null;
    
        public void push(int x) {
            stack.add(x);
            if(min !=null){
                if(x < min){
                    min = x;
                }
            }
        }
    
        public void pop() {
            int temp = stack.get(stack.size()-1);
            if(min !=null && temp == min){
                min = null;
            }
            stack.remove(stack.size()-1);
        }
    
        public int top() {
            return stack.get(stack.size()-1);
        }
    
        public int getMin() {
            if(min != null){
                return min;
            }
            min = stack.get(0);
            for(int i=1;i<stack.size();i++){
                int temp = stack.get(i);
                if(temp < min){
                    min = temp;
                }
            }
            return min;
        }

  • 1
    L

    Hmm, the question requires that we should call getMin() in constant time, but you put a loop which may cost O(n) time in the method. Is that really OK?


  • 0
    A

    Use two stack is better , but there must be some way more faster


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.