• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

JS Leetcode 155. 最小栈 题解分析

开发技术 开发技术 3小时前 3次浏览

壹 ❀ 引

本题来自LeetCode155. 最小栈,难度简单,题目描述如下:

设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。

push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。

示例:

输入:

["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.

提示:

pop、top 和 getMin 操作总是在 非空栈 上调用。

贰 ❀ 使用数组API模拟

题目要求其实很简单,自己实现一个支持入栈,出栈,获取栈顶元素以及获取栈内最小元素的栈结构。

我们都知道栈是先进后出,就像俄罗斯方块一样,先入栈的总是在栈底,所以出栈时,总是最后入栈的先出栈,最后出栈的总是最早入栈的元素。因此我们完全可以使用一个数组模拟这个过程,我们使用shift模拟出栈,使用unshift模拟入栈,top是获取栈顶元素,这里我们可以直接使用arr[0]来实现这个方法,抛开题目使用常数时间检索最小值的要求,其实我们可以使用Math.min来检索栈内最小元素。

废话不多说,先上一个基本实现的代码:

/**
 * initialize your data structure here.
 */
var MinStack = function() {
    this.nums = [];
};

/** 
 * @param {number} val
 * @return {void}
 */
MinStack.prototype.push = function(val) {
  	// 模拟入栈
    this.nums.unshift(val);
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
  	// 模拟出栈
    this.nums.shift();
};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
  	// 模拟top
    return this.nums[0];
};

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

以上代码能满足基本要求,但并未达到查找最小数时常数时间的要求。何为常数时间复杂度,其实就是O(1)。我们往栈内添加元素的行为只有一种,也就是push,所以如果要达到要求,其实可以在这一步做点小操作,比如每次入栈的时候都计算当前的最小值,并随着当前入栈的值组成一个新数组,一起入栈。

假设我们入栈操作一共做了三次,入栈的数字为1,3,0,那么这个过程就是:

1开始入栈了,由于此时是空栈,那么最小值就是1自己,于是我们入栈元素为[1,1],整个栈此时为[[1,1]]

3开始入栈了,此时栈并不是空栈,最小值自然是栈顶元素[1,1][1]与3做比较,很明显1更小,于是入栈[3,1],此时栈为[[3,1],[1,1]]

0开始入栈了,栈顶元素的第二个数字永远是当前栈的最小值,因此我们需要拿0和1比较,很明显0更小,于是入栈[0,0],此时栈为[[0,0],[3,1],[1,1]]

如果我们要获取当前栈最小元素,永远可以通过获取栈顶元素的第二个数字,它就是当前最小数。假设[0,0]出栈了,那么当前最小数就是1,完全没问题。

让我们实现这个代码:

/**
 * initialize your data structure here.
 */
var MinStack = function () {
    this.nums = [];
};

/** 
 * @param {number} val
 * @return {void}
 */
MinStack.prototype.push = function (val) {
  	// 假设是空栈,最小的就是自己,反之与栈顶元素的第二个数字进行比较
    if (this.nums.length) {
        this.nums.unshift([val, Math.min(val, this.nums[0][1])])
    } else {
        this.nums.unshift([val, val]);
    };
};

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

/**
 * @return {number}
 */
MinStack.prototype.top = function () {
    return this.nums[0][0];
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function () {
  	// 常数时间获取栈内最小值
    return this.nums[0][1];
};

那么本题就分析到这里了。


程序员灯塔
转载请注明原文链接:JS Leetcode 155. 最小栈 题解分析
喜欢 (0)