[LeetCode] 155. Min Stack, Medium

1. 문제

• 요구사항에 맞게 min stack을 구현하라.
• 모든 함수의 시간 복잡도는 O(1)이 되어야 한다.

2. 해결

class MinStack {
    stack: number[];
    minstack: number[];
    constructor() {
        this.stack = new Array();    
        this.minstack = new Array();    
    }

    push(val: number): void {
        this.stack.push(val);
        if(this.minstack.length === 0 || val <= this.minstack[this.minstack.length -1]) {
            this.minstack.push(val);
        } 
    }

    pop(): void {
        if(this.stack.pop() === this.minstack[this.minstack.length -1]) {
            this.minstack.pop();
        }
    }

    top(): number {
        return this.stack[this.stack.length - 1];
    }

    getMin(): number {
        return this.minstack[this.minstack.length -1];
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * var obj = new MinStack()
 * obj.push(val)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.getMin()
 */

• 최소값 관리에 막혔는데, 별도로 배열을 한 개 더 둬서 관리하면 된다.