方法一：使用辅助栈
题目要求各种操作的时间复杂度都为O(1)，所以要想到用空间换时间的方向，用一个辅助栈来记录数据栈每次更新时的最小值的变化情况。
1 /** 2 * initialize your data structure here. 3 */ 4 var MinStack = function() { 5 this.dataStack = []; 6 this.minDataStack = [Infinity];//Infinity的作用是当第一次比较时即有值可比 7 }; 8 9 /** 10 * @param {number} x 11 * @return {void} 12 */ 13 MinStack.prototype.push = function(x) { 14 this.dataStack.push(x); 15 this.minDataStack.push(Math.min(x, this.minDataStack[this.minDataStack.length - 1])); 16 }; 17 18 /** 19 * @return {void} 20 */ 21 MinStack.prototype.pop = function() { 22 this.dataStack.pop(); 23 this.minDataStack.pop(); 24 }; 25 26 /** 27 * @return {number} 28 */ 29 MinStack.prototype.top = function() { 30 return this.dataStack[this.dataStack.length - 1]; 31 }; 32 33 /** 34 * @return {number} 35 */ 36 MinStack.prototype.min = function() { 37 //console.log(this.dataStack.length); 38 //console.log(this.minDataStack); 39 return this.minDataStack[this.dataStack.length]; //return this.minDataStack[this.minDataStack.length - 1]; 40 }; 41 42 /** 43 * Your MinStack object will be instantiated and called as such: 44 * var obj = new MinStack() 45 * obj.push(x) 46 * obj.pop() 47 * var param_3 = obj.top() 48 * var param_4 = obj.min() 49 */
Infinity的用法
暂时不太清楚。 //2021.9.1
方法二：记录差值
数据栈中记录当前元素与最小值的差值，通过栈中数据的正负来判断数据是否为最小值，栈中第一个数据需要特殊处理。
1 /** 2 * initialize your data structure here. 3 */ 4 var MinStack = function() { 5 this.dataStack = []; 6 this.min_val = 0; 7 }; 8 9 /** 10 * @param {number} x 11 * @return {void} 12 */ 13 MinStack.prototype.push = function(x) { 14 //若栈为空 15 if(this.dataStack.length == 0) { 16 this.dataStack.push(x); 17 this.min_val = x; 18 }else {//栈不为空 19 //记录x与min_val的差值 20 this.dataStack.push(x - this.min_val); 21 //更新最小值 22 this.min_val = Math.min(x, this.min_val); 23 //console.log(this.min_val); 24 } 25 26 }; 27 28 /** 29 * @return {void} 30 */ 31 MinStack.prototype.pop = function() { 32 //若当前栈中数据小于0，则表示出栈后最小值需要更新 33 if(this.dataStack[this.dataStack.length - 1] < 0) { 34 this.min_val -= this.dataStack[this.dataStack.length - 1]; 35 } 36 this.dataStack.pop(); 37 }; 38 39 /** 40 * @return {number} 41 */ 42 MinStack.prototype.top = function() { 43 if(this.dataStack.length == 1) { 44 //若此时栈长度为1 45 return this.dataStack[this.dataStack.length - 1]; 46 }else if (this.dataStack[this.dataStack.length - 1] > 0) { 47 //若此时栈顶元素为正，即表示栈顶元素不是最小值 48 return this.dataStack[this.dataStack.length - 1] + this.min_val; 49 }else { 50 return this.min_val; 51 } 52 }; 53 54 /** 55 * @return {number} 56 */ 57 MinStack.prototype.min = function() { 58 return this.min_val; 59 }; 60 61 /** 62 * Your MinStack object will be instantiated and called as such: 63 * var obj = new MinStack() 64 * obj.push(x) 65 * obj.pop() 66 * var param_3 = obj.top() 67 * var param_4 = obj.min() 68 */