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

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

题目来源

来源：力扣（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.
1
2
3
4
5
6
7
8

题目分析

栈的特点是后进先出，在 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, 5
stack [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] // 出栈元素是 5
minStack [2, 1] // 最小元素无变化

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

stack [2] // 出栈元素是 3
minStack [2] // 最小元素无变化

stack [] // 出栈元素是 2
minStack [] // 2 出栈，栈空，无最小元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

代码实现

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();
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

执行结果

复杂度分析

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

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

总结

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