栈和队列
leetcode155. 最小栈
2021-05-19 390 1
简介 leetcode155. 最小栈,力扣链接地址:https://leetcode-cn.com/problems/min-stack/
1. 最小栈解题思路
1.1 原生的栈
C++/Java/Python 支持的栈(原生栈),可以实现 push、pop、top(peek), 但是要获取最小元素, 一种方法是通过暴力搜索,从头到尾遍历整个,那么时间复杂度是 O(n),不是在常数级获取最小值, 不符合题目的要求。
我们可以设置两个栈,一个数据栈 datastack,用于存放需要存放的数据,一个记录最小值的栈 sortedstack。
每次 push 操作之后, 保存当前 push 元素之后数据栈中的最小值, 因为从第一次 push 到之后的每次 push 操作,我们知道每次 push 的值,也很容易知道当前的栈中的最小值。
1.2 绘解过程
给定一组数据,依次 push 到数据栈 datastack 中,每次 push 操作之后,也将最小值 push 到 sortedstack 中
最终所有的数据 push 到 datastack 之后
数据栈 datastack 出栈的时候, 同时也将 sortedstack 出栈, 那么 sortedstack 栈顶就是当前数据栈 datastack 的最小值, 常数级获取最小值。----空间换取时间
1.3 优化
我们发现, sortedstack 存在重复值, 那么可以在每次数据栈入栈时, 如果 当前元素 <= sortedstack 的栈顶, 那么也将元素压入 sortedstack
数据栈出栈时, 当前出栈的元素 = sortedstack 的栈顶, 那么两个栈都出栈。
比如:
要入栈的4 <= sortedstack 的栈顶 7, 那么将4压入 sortedstack
4 <= 4,也将4压入 sortedstack
整个过程的逻辑,动图如下:
如果动图太快,可以点击视频观看,可以暂停:
// C++
class
MinStack {
public
:
/** initialize your data structure here. */
stack<
int
> dataStack;
// 数据栈
stack<
int
> sortedStack;
// 有序栈(栈底最大,栈顶最小,有 <= 栈顶的元素才进行push)
MinStack() {
}
void
push(
int
val) {
dataStack.push(val);
// --有序栈
// ----如果为空 则 push
// ----如果val 不大于 当前栈顶 则 push
if
(sortedStack.empty() || val <= sortedStack.top())
sortedStack.push(val);
}
void
pop() {
// 数据栈的栈顶如果与 有序栈的栈顶相等, 那么都出栈
if
(dataStack.top() == sortedStack.top())
sortedStack.pop();
dataStack.pop();
}
int
top() {
return
dataStack.top();
}
int
getMin() {
return
sortedStack.top();
}
};
// Java
class
MinStack {
/** initialize your data structure here. */
Stack<Integer> dataStack =
new
Stack<Integer> ();
Stack<Integer> sortedStack =
new
Stack<Integer> ();
public
MinStack() {
}
public
void
push(
int
val) {
dataStack.push(val);
// --有序栈
// ----如果为空 则 push
// ----如果val 不大于 当前栈顶 则 push
if
(sortedStack.empty() || val <= sortedStack.peek())
sortedStack.push(val);
System.out.println(sortedStack);
}
public
void
pop() {
// 数据栈的栈顶如果与 有序栈的栈顶相等, 那么都出栈
// 注意 Stack中存储的是 Integer 对象 这里不能用 ==
if
(dataStack.peek().equals(sortedStack.peek()))
sortedStack.pop();
dataStack.pop();
}
public
int
top() {
return
dataStack.peek();
}
public
int
getMin() {
return
sortedStack.peek();
}
}
# Python
class
MinStack:
def
__init__(
self
):
"""
initialize your data structure here.
"""
self
.datastack
=
[]
# 数据栈
self
.sortedstack
=
[]
# 有序栈(栈底最大,栈顶最小,有 <= 栈顶的元素才进行push)
def
push(
self
, val:
int
)
-
>
None
:
self
.datastack.append(val)
# --有序栈
# ----如果为空 则 push
# ----如果val 不大于 当前栈顶 则 push
if
not
self
.sortedstack
or
self
.sortedstack[
-
1
] >
=
val:
self
.sortedstack.append(val)
def
pop(
self
)
-
>
None
:
# 数据栈的栈顶如果与 有序栈的栈顶相等, 那么都出栈
if
self
.datastack[
-
1
]
=
=
self
.sortedstack[
-
1
]:
self
.sortedstack.pop()
self
.datastack.pop()
def
top(
self
)
-
>
int
:
return
self
.datastack[
-
1
]
def
getMin(
self
)
-
>
int
:
return
self
.sortedstack[
-
1
]