当前位置：首页 > article >正文

一起学习LeetCode热题100道（70/100）

article 2024/11/15 7:50:22

70.最小栈(学习)

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

示例 1:
输入：
[“MinStack”,“push”,“push”,“push”,“getMin”,“pop”,“top”,“getMin”]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.

提示：
-231 <= val <= 231 - 1
pop、top 和 getMin 操作总是在非空栈上调用
push, pop, top, and getMin最多被调用 3 * 104 次

解析：
一、构造函数 MinStack
1.首先，我们定义了一个名为MinStack的函数，这个函数作为构造函数来创建新的栈实例。在JavaScript中，构造函数通常是一个普通函数，但它被设计为使用new关键字来调用，以创建一个新的对象实例。
2.在这个构造函数中，我们为即将创建的对象实例初始化了两个属性：stack和minStack。这两个数组分别用于存储栈中的元素和每个状态下的最小值。

二、原型链和方法定义
1.在JavaScript中，每个函数都有一个特殊的属性prototype，它是一个对象，用于为通过该函数创建的实例提供共享的方法和属性。当我们尝试访问一个实例的某个属性或方法时，如果该实例本身没有这个属性或方法，JavaScript引擎就会沿着原型链向上查找，直到找到该属性或方法或到达原型链的顶端（Object.prototype）。
2.在上述代码中，我们为MinStack.prototype添加了四个方法：push、pop、top和getMin。这些方法将被所有通过new MinStack()创建的实例共享。每个实例都可以调用这些方法，但它们实际上是在MinStack.prototype上定义的。

三、方法的实现细节
1.push(val)：该方法将一个新元素val添加到stack数组中。同时，如果minStack为空，或者val小于等于minStack的栈顶元素，则将val也添加到minStack中。这样，minStack的栈顶元素就始终表示当前栈中的最小值。
2.pop()：该方法从stack数组中移除并返回栈顶元素。如果移除的元素等于minStack的栈顶元素，则从minStack中也移除该元素。这确保了minStack的栈顶元素始终有效。
3.top()：该方法返回stack数组的栈顶元素，但不从栈中移除它。
4.getMin()：该方法返回minStack的栈顶元素，即当前栈中的最小值。

var MinStack = function () {
    this.stack = []; // 主栈，用于存储所有元素  
    this.minStack = []; // 辅助栈，用于存储每个状态下的最小值  
};

/** 
 * @param {number} val
 * @return {void}
 */
MinStack.prototype.push = function (val) {
    this.stack.push(val); // 将元素推入主栈  
    // 如果辅助栈为空，或者新元素小于等于辅助栈的栈顶元素，则也将该元素推入辅助栈  
    if (this.minStack.length === 0 || val <= this.minStack[this.minStack.length - 1]) {
        this.minStack.push(val);
    }
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function () {
    if (this.stack.length === 0) {
        throw new Error('Stack is empty');
    }
    const topVal = this.stack.pop(); // 弹出主栈的栈顶元素  
    // 如果弹出的元素等于辅助栈的栈顶元素，则也弹出辅助栈的栈顶元素  
    if (topVal === this.minStack[this.minStack.length - 1]) {
        this.minStack.pop();
    }
};

/**
 * @return {number}
 */
MinStack.prototype.top = function () {
    if (this.stack.length === 0) {
        throw new Error('Stack is empty');
    }
    return this.stack[this.stack.length - 1]; // 返回主栈的栈顶元素  
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function () {
    if (this.minStack.length === 0) {
        throw new Error('Stack is empty');
    }
    return this.minStack[this.minStack.length - 1]; // 返回辅助栈的栈顶元素，即当前最小值  
};