155. Min Stack

Leetcode link

题目简介

var MinStack = function() {};

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

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

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

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

题目要求我们实现一个 MinStack 数据结构

除了常规的 push pop top 之外，还需要能在 O(1) 的复杂度下取得当前 stack 中的最小值

解题思路

我们在入栈的时候，将当前栈中的最小元素值与入栈元素一起入栈

当我们需要查找最小值的时候，只需要去栈顶元素中找到最小值返回即可

Javascript

var MinStack = function () {
    this.stack = []
};

/** 
 * @param {number} val
 * @return {void}
 */
MinStack.prototype.push = function (val) {
    const min = this.getMin()
    if (min === null || min > val) {
        this.stack.push([val, val])
    } else {
        this.stack.push([val, min])
    }
};

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

/**
 * @return {number}
 */
MinStack.prototype.top = function () {
    return this.stack.length ? this.stack[this.stack.length - 1][0] : null
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function () {
    return this.stack.length ? this.stack[this.stack.length - 1][1] : null
};

/** 
 * Your MinStack object will be instantiated and called as such:
 * var obj = new MinStack()
 * obj.push(val)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.getMin()
 */