Unusual solution for Min Stack get Memory Limit Exceeded


  • 2
    O

    I know this question got asked often, but I think my solution is a little bit of different.
    Note: I used Java.
    What I do is maintaining 2 Arraylist<Integer>, one for storing data, and another for storing index of the data which used to be a min.
    For example: if my data stack currently has: 10,8,5,5,5,2. Then my index stack now has:0,1,2,5.

    The common factor causing MLE is that the duplicate min are store multiple times, while in my case, only one time.
    I can not see what is wrong in my program or why it exceeds the space limit.

    One possible reason I can figure is the cost of using ArrayList is higher than int[] or Stack...

    Any suggestion is appreciated!

    The code:

    List<Integer> list = new ArrayList<Integer>();
    List<Integer> min = new ArrayList<Integer>();
    
    public void push(int x) {
        if(list.size()==0){
            min.add(0);
        }
        else if(list.get(min.get(min.size()-1)) > x){
            min.add(list.size());
        }
        list.add(x);
    }
    
    public void pop() {
        if(list.size() != 0){
            if(list.size()-1 == min.get(min.size()-1)){
                min.remove(min.size()-1);
            }
            list.remove(list.size()-1);
        }
    }
    
    public int top() {
        if(list.size() != 0){
            return list.get(list.size()-1);
        }
        return 0;
    }
    
    public int getMin() {
        if(list.size() != 0){
            return list.get(min.get(min.size()-1));
        }
        return 0;
    }

  • 0
    V

    When push the number which is the same with the minimum one, Do you remember updating your index array list?


  • 0
    O

    I didn't Because I just need to keep track of the index of the first minimum, if there are multiple minimums that have the same value. As in the example, I have pushed three 5 into stack, however, I only pushed the index of the first 5, which is 2, into the index stack. In this sense, when I do top(), I return the value of which the last index pointing to.


Log in to reply
 

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