stack에서 minMax를 저장하는 방법

알고리즘을 풀다보니 stack 구조를 만들고 push, pop, peek(마지막에 push한 것 보여주기), getMin(현재 stack에서의 min 값 가져오기), getMax(현재 stack에서의 Max 값 가져오기)를 구현해야하는 것이 있었다.

처음에는 그럼 array 를 2개 만들어
stack(첫번째 array)는 일반적인 stack 으로
sortedArray(두번째 array)는 정렬이된 array를 만들어야 겠다고 생각했다.

하지만 작성하다보니 이렇게 구조를 만들 경우,
push 할 때는 sortedArray 훑어 알맞은 장소에 넣어야 하고(BigO(N))
pop 할 때도 sortedArray에서 전체를 훑어 마지막에 넣은 요소를 찾고(BigO(N)) 그리고 splice까지 한다면 (BigO(N)) 여야 했다...

그래서 더 나은 방법이 있을 것이라 생각했는데 대박!
sortedArray가 아닌 minMaxStack 으로 만들면 됐다.
minMaxStack은 말 그대로 요소가 들어갈 때마다 새로운 minMax를 만들어 stack처럼 쌓는 것이다.
그렇게 하면 push할 때도 BigO(1) pop할 때도 BigO(1)이다. 물론 push가 엄청날 경우 문제가 될 수 있지만 space가 BigO(N)정도라면 나쁘지 않아 보인다.

  push(number) {
    const newMinMax = { min: number, max: number };
    if (this.minMax.length) {
      const lastMinMax = this.minMax[this.minMax.length - 1];
      newMinMax.min = Math.min(newMinMax.min, lastMinMax.min);
      newMinMax.max = Math.max(newMinMax.max, lastMinMax.max);
    }
    this.minMax.push(newMinMax);
    this.stack.push(number);
  }

뭔가 실행 컨텍스트 느낌도 나고 ㅎㅎㅎ 사고가 또 확장된 느낌이 든다!