【剣指Offer】30.min関数を含むスタック(JS実装)
テーマの説明
スタックのデータ構造を定義し、このタイプにおいて、スタックを得ることができる最小要素のmin関数を実現してください.このスタックにおいて、min、pushおよびpopを呼び出す時間の複雑さはすべてO(1)です.
例:
二つのスタックを定義し、データスタックはデータを保存し、補助スタックは毎回の最小値を保存します.
操作
データースタック
補助倉庫
最小値
押し込み3
3
3
3
押し込み4
3 4
3
3
押し込み2
3 4 2
3 3 2
2
ポップアップ2
3 4
3
3
スタックのデータ構造を定義し、このタイプにおいて、スタックを得ることができる最小要素のmin関数を実現してください.このスタックにおいて、min、pushおよびpopを呼び出す時間の複雑さはすべてO(1)です.
例:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min(); --> -3.
minStack.pop();
minStack.top(); --> 0.
minStack.min(); --> -2.
二つのスタックを定義し、データスタックはデータを保存し、補助スタックは毎回の最小値を保存します.
操作
データースタック
補助倉庫
最小値
押し込み3
3
3
3
押し込み4
3 4
3
3
押し込み2
3 4 2
3 3 2
2
ポップアップ2
3 4
3
3
var MinStack = function() {
this.dataStack = [];
this.minStack = [];
//var min;
};
/**
* @param {number} x
* @return {void}
*/
MinStack.prototype.push = function(x) {
this.dataStack.push(x);
if( this.minStack.length == 0 || x < this.minStack[this.minStack.length-1] )
{
this.minStack.push(x);
}
else{
this.minStack.push(this.minStack[this.minStack.length-1]);
}
};
/**
* @return {void}
*/
MinStack.prototype.pop = function() {
this.dataStack.pop();
this.minStack.pop();
};
/**
* @return {number}
*/
MinStack.prototype.top = function() {
return this.dataStack[this.dataStack.length-1];
};
/**
* @return {number}
*/
MinStack.prototype.min = function() {
return this.minStack[this.minStack.length-1];
};