155. Min Stack

💡 풀이

// 시간 복잡도: O(N)
// 처음 풀이
class MinStack {
  constructor() {
    this.stack = [];
  }
  push(x) {
    return this.stack.push(x);
  }
  pop() {
    return this.stack.pop();
  }
  top() {
    return this.stack[this.stack.length - 1];
  }
  getMin() {
    return Math.min(...this.stack);
  }
}


// 시간 복잡도: O(1)
// 두 번째 풀이.
class MinStack {
  constructor() {
    this.stack = [];
    this.min = Infinity;
  }
  push(x) {
    const node = { val: x, prevMin: this.min };
    this.stack.push(node);
    this.min = Math.min(this.min, x);
  }
  pop() {
    const { val, prevMin } = this.stack.pop();
    this.min = prevMin;
    return val;
  }
  top() {
    return this.stack[this.stack.length - 1].val;
  }
  getMin() {
    return this.min;
  }
}

📝 정리

getMin()을 구하는게 주된 문제인데, 난 처음엔 단순히 Math.min(...this.stack)을 사용했다가 시간이 너무 높게 나와서 다른 방법이 있을 것 같아서 생각을 해봤다.

두 번째 풀이는, node라는 객체를 하나 만들어 준다. 객체의 프로퍼티로는 val 값과 prevMin값을 줬다. min값을 push와 pop을 할 때마다 변화시킬 것이기 때문에 따로 저장해줬다.

그리고 push를 할 때마다 Math.min() 메서드를 통해 현재의 val 값과 현재의 min 값을 비교해 새로 min값을 업데이트 해준다.

pop을 할 때는 prevMin으로 this.min값을 업데이트 해준다.

수정, 지적을 환영합니다!

문제 링크

https://leetcode.com/problems/min-stack/submissions/

LeetCode GitHub

https://github.com/tTab1204/LeetCode