LeetCode 155 - Min Stack (Easy)

문제

LeetCode - 155번

풀이 과정

스택 을 사용해서 min stack 을 구현하는 문제입니다.

단순하게 구현하면 최소값을 찾을 때마다 Math.min 을 사용할 수도 있지만
문제 조건과 같이 상수 시간에 최소값을 찾기 위해서는 다른 방법이 필요합니다.

이를 위해 두 개의 스택을 사용하여 값을 저장하도록 합니다.
하나는 들어온 순서대로 쌓아 올리는 스택이고 다른 하나는 이에 대응하여 현재까지의 최소값을 저장하는 스택으로 사용합니다.

예를 들어 1, 2, 0, 3 이 순서대로 입력된다고 한다면 두 개의 스택은 다음과 같은 상태를 가지게 됩니다.

| 3 | | 0 |
| 0 | | 0 |
| 2 | | 1 |
| 1 | | 1 |
A 스택 B 스택

따라서 minValue 를 통해 현재까지의 최소값을 갱신하면서 B 스택의 push, pop 을 구현합니다.

코드

/**
 * initialize your data structure here.
 */
var MinStack = function () {
  this.stack = [];
  this.minStack = [];
  this.minValue = Infinity;
};

/**
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function (x) {
  this.stack.push(x);
  this.minValue = Math.min(this.minValue, x);
  this.minStack.push(this.minValue);
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function () {
  this.stack.pop();
  this.minStack.pop();

  if (this.minStack.length > 0) {
    this.minValue = this.minStack[this.minStack.length - 1];
  } else {
    this.minValue = Infinity;
  }
};

/**
 * @return {number}
 */
MinStack.prototype.top = function () {
  return this.stack[this.stack.length - 1];
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function () {
  return this.minValue;
};