【刷算法】LeetCode.155-最小栈

wing324 发布于2019-08-23 11:31 / 1289人阅读

摘要：题目描述设计一个支持，，操作，并能在常数时间内检索到最小元素的栈。删除栈顶的元素。检索栈中的最小元素。示例返回返回返回代码实现

题目描述

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

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

示例:

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

代码实现

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

/** 
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function(x) {
  let s2 = this.s2,
      s2Len = s2.length,
      s1 = this.s1;
  
  
  let curMin = s2[s2Len-1];
  if(curMin < x)
    s2.push(curMin);
  else
    s2.push(x);
  s1.push(x);
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
  let s1 = this.s1,
      s1Len = s1.length,
      s2 = this.s2,
      s2Len = s2.length;
  
  if(s1Len === 0)
    return undefined;
  
  s2.pop();
  return s1.pop();
};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
   let s1 = this.s1,
      s1Len = s1.length;
  if(s1.length === 0)
    return undefined;
  return s1[s1Len-1];
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
  let s2 = this.s2,
      s2Len = s2.length;
  if(s2Len === 0)
    return undefined;
  
  return s2[s2Len-1];
};

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

GPU云服务器云服务器最小覆盖算法最小哈希算法最小划分算法最小环算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/97084.html

LeetCode 155：最小栈 Min Stack

摘要：删除栈顶的元素。可以另外新建一个栈来顺序存入数据最小值。另外在数据入栈时需要判断该值是否比辅助栈的栈顶元素的值更小，如果更小，也应该将它加入辅助栈。并且需要判断辅助栈是否为空，在不空的条件下才可以取栈顶元素比较，否则会溢出。 LeetCode 155：最小栈 Min Stack 设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。 push(x) -- ...

LeexMuller 2019-08-19 10:16 评论0 收藏0
力扣(LeetCode)155

摘要：题目地址题目描述设计一个支持，，操作，并能在常数时间内检索到最小元素的栈。将元素推入栈中。删除栈顶的元素。示例返回返回返回解答每次入栈都放入两个元素，分别是当前元素，和当前的最小元素因此放入之前需要和当前值进行比较。题目地址：https://leetcode-cn.com/probl...题目描述：设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。 p...

Scliang 2019-08-16 15:21 评论0 收藏0
【刷算法】包含min函数的栈

摘要：题目描述定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的函数。题目描述定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。分析该题目要求实现一个带有返回当前栈中最小元素功能的数据结构，首先会想到使用一个变量保存当前最小元素的下标，但是仔细一想，如果当前最小元素刚好在栈顶，此时执行pop操作，那么最小元素会被弹出，新的最小元素又上哪儿找呢？比较暴力的方...

justCoding 2019-08-22 18:21 评论0 收藏0
从简历被拒到收割今日头条 offer，我用一年时间破茧成蝶！

摘要：正如我标题所说，简历被拒。看了我简历之后说头条竞争激烈，我背景不够，点到为止。。三准备面试其实从三月份投递简历开始准备面试到四月份收，也不过个月的时间，但这都是建立在我过去一年的积累啊。本文是无精疯同学投稿的面试经历关注微信公众号：进击的java程序员K，即可获取最新BAT面试资料一份在此感谢无精疯同学的分享目录：印象中的头条面试背景准备面试 ...

tracymac7 2019-08-15 17:57 评论0 收藏0