stackでminMaxを保存する方法


アルゴリズムを解くには、スタック構造を作成し、push、pop、peek(最後のpushを表示)、getMin(現在のスタックの最小値を取得)、getMax(現在のスタックのMax値を取得)を実現する必要があります.
最初に2つのarrayを作成
stack(最初のarray)は普通のstackです.
sortedArray(2番目のarray)は、整列したarrayを作成すべきだと考えています.
ただし、作成中にこの構造が作成された場合、
Pushの場合は、sortedArrayをブラウズして適切な位置に入れる(BigO(N)
popの時もsortedArrayで最後に入れた元素(BigO(N)を探して、またつなぎ合わせるなら(BigO(N))...
だからもっといい方法があると思っていたのに、大発!
sortedArrayではなく、minMaxStackです.
minMaxStackというように、要素を加えるたびに新しいminMaxが作成され、スタックのように積み上げられます.
このように押すと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);
  }
コンテキストを実行する感じがして、ほほほ、事故がまた広がったような気がします!