搜文章
推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > 飘飞的心灵 > 【程序员面试金典】【栈】面试题 03.02 - 栈的最小值

【程序员面试金典】【栈】面试题 03.02 - 栈的最小值

飘飞的心灵 2020-07-14

一 目录

不折腾的前端,和咸鱼有什么区别

目录
一 目录
二 题目
三 解题思路
四 统计分析
五 解题套路

二 题目

请设计一个栈,除了常规栈支持的pop与push函数以外,还支持min函数,该函数返回栈元素中的最小值。执行push、pop和min操作的时间复杂度必须为O(1)。


示例:

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/min-stack-lcci
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
/**
 * initialize your data structure here.
 */

var MinStack = function({

};

/** 
 * @param {number} x
 * @return {void}
 */

MinStack.prototype.push = function(x{

};

/**
 * @return {void}
 */

MinStack.prototype.pop = function({

};

/**
 * @return {number}
 */

MinStack.prototype.top = function({

};

/**
 * @return {number}
 */

MinStack.prototype.getMin = function({

};

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

根据上面的已知函数,小伙伴们可以先尝试破解本题,确定了自己的答案后再看下面代码。

三 解题思路

设计题,直接上代码:

var MinStack = function({
  this.stack = [];
  this.sortStack = [];
  this.length = 0;
};

MinStack.prototype.push = function(x{
  const length = this.length;
  this.stack[length] = x;
  // 通过辅助栈,记录每次添加的时候,要如何判断最小值
  // sortStack 最末尾一项为添加之前的最小的值
  if (!length || this.sortStack[length - 1] > x) {
    this.sortStack[length] = x;
  } else {
    this.sortStack[length] = this.sortStack[length - 1];
  }
  this.length = length + 1;
};

MinStack.prototype.pop = function({
  const length = this.length;
  this.length = length - 1;
  return this.stack[length - 1];
};

MinStack.prototype.top = function({
  return this.stack[this.length - 1];
};

MinStack.prototype.getMin = function({
  return this.sortStack[this.length - 1];
};

四 统计分析

本题不需要统计分析。

五 套路分析

本题暂未发现任何套路,如果有但是 jsliang 后面发现了的话,会在 GitHub 进行补充。

如果小伙伴有更好的思路想法,或者没看懂其中某种解法,欢迎评论留言或者私聊 jsliang~


不折腾的前端,和咸鱼有什么区别!

jsliang 会每天更新一道 LeetCode 题解,从而帮助小伙伴们夯实原生 JS 基础,了解与学习算法与数据结构。

浪子神剑 会每天更新面试题,以面试题为驱动来带动大家学习,坚持每天学习与思考,每天进步一点!

jsliang 的文档库 由 梁峻荣 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
基于https://github.com/LiangJunrong/document-library上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/licenses/by-nc-sa/2.5/cn/ 处获得。


版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《【程序员面试金典】【栈】面试题 03.02 - 栈的最小值》的版权归原作者「飘飞的心灵」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注飘飞的心灵微信公众号

飘飞的心灵微信公众号:gh_e57c56f669b2

飘飞的心灵

手机扫描上方二维码即可关注飘飞的心灵微信公众号

飘飞的心灵最新文章

精品公众号随机推荐