[leetcode] 155. Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

• MinStack() initializes the stack object.
• void push(int val) pushes the element val onto the stack.
• void pop() removes the element on the top of the stack.
• int top() gets the top element of the stack.
• int getMin() retrieves the minimum element in the stack.

You must implement a solution with O(1) time complexity for each function.

 

Example 1:

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

 

Constraints:

• -231 <= val <= 231 - 1
• Methods pop, top and getMin operations will always be called on non-empty stacks.
• At most 3 * 104 calls will be made to push, pop, top, and getMin.

 

풀이 - 1

기존에 실습해보았던 코드를 응용해보았다.

class MinStack {
  private stack: Array<number>;
  private minArr: Array<number>;
  private topIdx: number;

  constructor() {
    this.stack = new Array<number>();
    this.minArr = new Array<number>();
    this.topIdx = -1;
  }

  push(val: number): void {
    this.topIdx++;
    this.stack[this.topIdx] = val;

    if (!this.minArr.length || this.getMin() >= val) {
      this.minArr.push(val);
    }
  }

  pop(): void {
    if (this.topIdx < 0) {
      throw new Error("Stack Underflow Exception!");
    }

    if (this.stack[this.topIdx] === this.getMin()) {
      this.minArr.pop();
    }
    this.stack[this.topIdx] = NaN;
    this.topIdx--;
  }

  top(): number {
    return this.stack[this.topIdx];
  }

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

기존에는 push, pop만 구현한 코드였는데, 거기에 최소값을 가져오기위한 배열을 만들어서 시간복잡도를 O(1) 조건에 맞게 풀었다.