Leetcode MinStack 설계 문제: JavaScript 저수준 솔루션

이 포스트에서는 MinStack이라고 하는 leetcode에서 가장 인기 있는 디자인 문제 중 하나에 대한 저수준 Javascript 솔루션을 공유하고 싶습니다. 이 문제는 푸시, 팝, 상단 및 일정한 시간에 최소 요소 검색을 지원하는 스택을 기대합니다. .
여기에서는 Javascript의 length , Math.min() , push , pop 등을 사용하는 대신 예상되는 기능을 가능한 한 낮은 수준으로 작성합니다.

/**
 * initialize data structure
 */
var MinStack = function () {

    this.stack = [];
    this.minVals = [];
    this.count = 0;
    this.min = Number.MAX_VALUE;
};

/** 
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function (x) {

    if (x < this.min || this.count === 0) {
        this.min = x;
    }

    this.minVals[this.count] = this.min;
    this.stack[this.count] = x;
    this.count++;

};

/**
 * @return {void}
 */
MinStack.prototype.pop = function () {

    delete this.stack[this.count - 1];
    delete this.minVals[this.count - 1];
    this.min = this.minVals[this.count - 2];
    this.count--;


};

/**
 * @return {number}
 */
MinStack.prototype.top = function () {

    return this.stack[this.count - 1]

};

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

    if (this.count > 0)
        return this.minVals[this.count - 1];

    else if (this.count === 0)
        return this.MinVals[0]
};

민스택:

스택: 값의 저장, 즉 스택

minVals: 최소값에 대한 저장소입니다. pop() 작업 후에 스택의 최소값을 삭제할 수 있으므로 최소값도 추적해야 하기 때문에 필요합니다.

개수: Javascript의 length를 사용하는 대신 this.count를 사용하여 마지막 인덱스를 설정하고 스택의 마지막 값 값을 얻을 수 있습니다.

min: Javascript에서 최대 숫자 값으로 시작하는 일종의 초기 및 전역 최소값입니다.

푸시(x):

스택에 요소를 추가합니다. 값을 반환하지 않습니다.
여기서 new element(x)를 스택에 추가하는 동안 새 요소가 this.min 값보다 작은지 확인합니다. 또한 스택이 비어 있으면 this.count===0 를 의미하는 경우도 포함합니다. 물론 this.minVals 의 첫 번째 요소도 새 요소(x)와 동일합니다. 스택의 두 길이는 count 값과 같습니다.
그런 다음 push() 함수에서 Javascript의 빌드를 사용하는 대신 스택의 마지막 요소가 새 요소라고 말합니다.

...

    if (x < this.min || this.count === 0) {
        this.min = x;
    }

    this.minVals[this.count] = this.min;
    this.stack[this.count] = x;
    this.count++;

팝():

스택에서 마지막 항목을 제거합니다. 우리는 자바스크립트의 pop() 함수를 사용하지 않을 것입니다. 스택에서 마지막 항목을 삭제하기만 하면 됩니다. 제거할 값이 배열의 최소값일 수 있다는 점을 고려해야 합니다. 그래서 실제로 minVals 대신 추가 this.min 스택이 필요한 이유입니다. 스택의 새로운 상태를 파악하려면 minVals 스택의 마지막 항목도 삭제해야 합니다. 하지만!
우리는 또한 위에 주어진 push(x) 함수로 스택에 새로운 값을 추가할 때 기억해야 합니다. 거기에서 x 값을 this.min 값과 비교하므로 this.min 값이 더 이상 this.minVals 스택의 마지막 항목이 아니라 이전 항목입니다. 마지막으로 스택에서 마지막 항목을 제거했으므로 카운트 수를 줄여 다음에 다른 작업을 수행할 때 카운트 값이 있는 스택의 마지막 인덱스를 따라야 합니다.

...
    delete this.stack[this.count - 1];
    this.min = this.minVals[this.count - 2];
    delete this.minVals[this.count - 1];
    this.count--;

맨 위():

스택의 마지막 항목을 반환합니다.
여기서 스택의 길이는 this.count이고 스택의 마지막 항목은 this.count-1의 인덱스에 있습니다.

 return this.stack[this.count - 1]

getMin():

스택의 최소값을 반환합니다. 여기에서는 전체 스택을 스캔하는 대신 이미 최소값을 항상 minStack로 설정했기 때문입니다. minStack의 마지막 항목을 편안하게 반환할 수 있습니다. 마지막 항목의 인덱스는 this.count-1 입니다. 그러나 이미 count=0에 있다면 minStack의 첫 번째 값을 반환해야 합니다.

...
if (this.count === 0)
        return this.MinVals[0]
    else
        return this.minVals[this.count - 1];