[LeetCode155题最小栈] | 刷题打卡

前言

本来想着今天的题解写今天的每日一题131. 分割回文串来着，但是我还没有特别明白，所以就没有写，就用掘金刷题打卡活动群里今天的推荐题来写吧??

题目描述

设计一个支持 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 操作总是在 非空栈 上调用。

解题思路

看完题目，其实应该明白这道题的解法了，特别是对前端来说，看见题目中描述的push、pop这两个方法就想到数组的方法。用数组stack来描述栈。

对于push、pop方法我们可以直接用数组的push和pop来做，但是我们要注意到题目中要求的检索最小元素，所以我们这里要把这个要求给考虑进来，用min_val来表示最小元素，初始值设为正无穷大。

push的时候用元素x和min_val来做比较，min_val取两者的最小值。

pop的时候判断数组末尾元素是否和min_val相等来更新min_val的值。

top的时候直接取数组的末尾元素就行了。

getMin的时候直接返回min_val就可以了。

解题代码

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

/** 
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function(x) {
  if (x <= this.min_val) {
    this.stack.push(this.min_val)
    this.min_val = x
  }
  this.stack.push(x)
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
  if (this.stack[this.stack.length - 1] === this.min_val) {
    this.stack.pop()
    this.min_val = this.stack[this.stack.length - 1]
    this.stack.pop()
  } else {
    this.stack.pop()
  }
};

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

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

刷题打卡记录

这里是之前的刷题打卡记录，大家有兴趣的可以看下，如果有什么不同的见解和看法或者觉得有什么错误的，欢迎在评论区留言！???

[LeetCode0303题区域和检索 - 数组不可变] | 刷题打卡

[LeetCode1200. 最小绝对差] | 刷题打卡

[LeetCode0304题二维区域和检索 - 矩阵不可变] | 刷题打卡

[LeetCode11题盛最多水的容器] | 刷题打卡

[LeetCode0338题比特位计数] | 刷题打卡

[LeetCode209题长度最小的子数组] | 刷题打卡

[LeetCode236题二叉树的最近公共祖先] | 刷题打卡

[LeetCode141题环形链表] | 刷题打卡

[LeetCode53题最大子序和] | 刷题打卡

[LeetCode48题旋转图像] | 刷题打卡

总结

多写写题解还是很有必要的，不要怕写的不好，写的过程就是回顾的过程，更容易加深自己的理解。

加油！hxdm！！！???

本文正在参与「掘金 2021 春招闯关活动」, 点击查看 活动详情