[力扣] 剑指 Offer 第一天 - 包含 min 函数的栈

作者：陈明勇

2022-11-15
广东
本文字数：1451 字
阅读完需：约 5 分钟

耐心和持久胜过激烈和狂热。

题目来源

来源：力扣（LeetCode）

链接：https://leetcode.cn/problems/bao-han-minhan-shu-de-zhan-lcof

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目描述

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

示例 1

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

复制代码

题目分析

栈的特点是后进先出，在 Go 语言里面可以使用切片实现栈。根据题意，结构体里不仅要定义一个栈变量 stack 去保存元素，还需要另一个栈 minStack，去维护 stack 里的最小元素，minStack 入栈条件是该元素小于或等于栈顶元素，这样一来最小的元素都会处于栈顶位置，而最小元素出栈的时机是当 stack 出栈的元素等于 minStack 的栈顶元素。

解题思路

对于入栈方法 push
先将元素 val 压入 stack。
然后判断 minStack 是否为空或 val 元素是否小于等于 minStack 的栈顶元素，条件成立则将 val 压入 minStack。
利用切片的特点，入栈通过 append 方法进行。
对于出栈方法 pop
将 stack 栈顶元素进行出栈，通过切片截取的方法，截取除了最后一个元素以外的区间，然后重新赋值给原切片，达到删除栈顶元素的效果。
然后判断被删除元素是否等于 minStack 栈顶元素，条件成立则 minStack 执行出栈操作

以下通过文字演示 stack 和 minStack 元素变化的过程

入栈顺序 2, 3, 1, 5stack [2]minStack [2]
stack [2, 3]minStack [2]
stack [2, 3, 1]minStack [2, 1]

stack [2, 3, 1, 5]minStack [2, 1]
出栈stack [2, 3, 1] // 出栈元素是 5minStack [2, 1] // 最小元素无变化
stack [2, 3] // 出栈元素是 1minStack [2] // 1 出栈，最小元素变更为 2
stack [2] // 出栈元素是 3minStack [2] // 最小元素无变化
stack [] // 出栈元素是 2minStack [] // 2 出栈，栈空，无最小元素

复制代码

代码实现

type MinStack struct {  stack, minStack []int}
/** initialize your data structure here. */func Constructor() MinStack {  return MinStack{}}
func (ms *MinStack) Push(x int) {  ms.stack = append(ms.stack, x)  if len(ms.minStack) == 0 || x <= ms.minStack[len(ms.minStack)-1] {    ms.minStack = append(ms.minStack, x)  }}
func (ms *MinStack) Pop() {  val := ms.stack[len(ms.stack)-1]  ms.stack = ms.stack[:len(ms.stack)-1]  if val == ms.minStack[len(ms.minStack)-1] {    ms.minStack = ms.minStack[:len(ms.minStack)-1]  }}
func (ms *MinStack) Top() int {  return ms.stack[len(ms.stack)-1]}
func (ms *MinStack) Min() int {  return ms.minStack[len(ms.minStack)-1]}

/** * Your MinStack object will be instantiated and called as such: * obj := Constructor(); * obj.Push(x); * obj.Pop(); * param_3 := obj.Top(); * param_4 := obj.Min(); */

复制代码

执行结果

复杂度分析

时间复杂度：push 方法时间复杂度为 O(1)，pop 方法时间复杂度 O(1)，都是常量级操作，最多调用栈操作两次。

空间复杂度：O(n)，其中 n 为总操作数。最坏情况下，stack 会连续压入 n 个元素，此时 stack 占用的空间为 O(n)。

总结

以上是本人的解法，如果对你有帮助，欢迎点赞收藏加关注，如果有错误的地方，欢迎指正！

发布于: 刚刚阅读数: 5

原文链接:【http://xie.infoq.cn/article/f05ccf0ab04295539b5f68e5f】。文章转载请联系作者。

陈明勇

关注

还未添加个人签名 2021-10-20 加入

还未添加个人简介

发布

暂无评论

创作场景

[力扣] 剑指 Offer 第一天 - 包含 min 函数的栈

题目来源

题目描述

示例 1

题目分析

解题思路

代码实现

执行结果

复杂度分析

总结

陈明勇

评论