Smart Accepted Java Solution - Linked List


  • 5
    R
    class Element{
        int value;
        int currentMin;
        Element next = null;
        Element(int value, int minBefore){
            this.value = value;
            this.currentMin = Math.min(minBefore,value);
     }
    
    Element top = null;
    public void push(int x) {
        Element newElement;
        if (top == null){
            newElement = new Element(x,x);
            top = newElement;
        }else{
            newElement = new Element(x,top.currentMin);
            newElement.next=top;
            top = newElement;
        }
    }
    
    public void pop() {
        if (top != null){
            top = top.next;
        }
    }
    
    public int top() {
        return top.value;
    }
    
    public int getMin() {
        return top.currentMin;
    }

  • 0
    L

    Save current min for every element is a kind of waste.


  • 0
    A

    yeah right,, but how do you find the new minimum value if the minimum value is popped?
    my solution is scanning the whole linkedList again to get the new minimum value, but I think it's also kinda waste...

    any better suggestion?


  • 0
    L

    Here is the main code:

    private Stack<Integer> value = new Stack<Integer>();
    private Stack<Integer> size = new Stack<Integer>();
    private Stack<Integer> min = new Stack<Integer>();
    MinStack() {
        size.push(0);
        min.push(Integer.MAX_VALUE);
        // "size" and "min" are working together.
        // if the numbers in "size" is: 0, 5, 9
        // and the numbers in "min" is: Integer.MAX_VALUE, 1, 3
        // that means, for those numbers which index is from 0 < index <= 5, the min value of them is 1;
        // for those numbers which index is from 5 < index <= 9, the min value of them is 3.
    }
    
    public void push(int x) {
        value.push(x);
        if (x < min.peek()) {
            min.push(x);
        } else {
            size.pop();
        }
        size.push(value.size());
    }
    
    public void pop() {
        value.pop();
        size.pop();
        if (value.size() > size.peek()) {
            size.push(value.size());
        } else {
            min.pop();
        }
    }

Log in to reply
 

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