It is my MinStack accepted solution(256ms).


  • 0
    O
    class MinStack {
    private int top;
    private int[] items;
    private int min;
    
    
    public MinStack() {
    	this.items = new int[100000];
    	this.top = -1;
    	this.min = 0;
    }
    public void push(int x) {
        if (this.top == this.items.length) {
        	System.out.println("Стек переполнен...");
        } else {
        	if (x <= this.items[this.min]) {
        		this.min = this.top + 1;
        	}
        	this.top++;
        	this.items[this.top] = x;
        }
    }
    
    public void pop() {
        this.items[this.top] = 0;
        this.top--;
    	if (this.min == this.top + 1) {
    		this.min = findMin();
    	}
    }
    
    public int findMin() {
    	int min = 0;
    	for(int i = 1; i <= this.top; i++) {
    		if (this.items[i] < this.items[min]) {
    			min = i;
    		}
    	}
    	
    	return min;
    }
    
    public int top() {
        return this.items[this.top];
    }
    
    public int getMin() {
        return this.items[this.min];
    }
    

    }


  • 0
    S

    Better use a linked list instead of fixed-length array.


  • 0
    O

    I think findMin () is not a constant-time function, this should not be accepted.


  • 0
    O

    You are right about function findMin but you should read problems and my code carefully. I return minimum value in constant time, but where I delete minimum value from the stack I need to find new minimum value. That is why I use findMin only in pop() function.


  • 0
    D

    in this case pop() is not constant then.


  • 0
    O

    Yes, You are right. In the worst case it is not constant but amortized time will be constant.


  • 0
    O

    Why do you think it is beter?


Log in to reply
 

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