mirror of
https://github.com/chefyuan/algorithm-base.git
synced 2024-12-27 04:46:17 +00:00
121 lines
4.4 KiB
Markdown
121 lines
4.4 KiB
Markdown
> 如果阅读时，发现错误，或者动画不可以显示的问题可以添加我微信好友 **[tan45du_one](https://raw.githubusercontent.com/tan45du/tan45du.github.io/master/个人微信.15egrcgqd94w.jpg)** ，备注 github + 题目 + 问题 向我反馈
|
||
>
|
||
> 感谢支持，该仓库会一直维护，希望对各位有一丢丢帮助。
|
||
>
|
||
> 另外希望手机阅读的同学可以来我的 <u>[**公众号：程序厨**](https://raw.githubusercontent.com/tan45du/test/master/微信图片_20210320152235.2pthdebvh1c0.png)</u> 两个平台同步，想要和题友一起刷题，互相监督的同学，可以在我的小屋点击<u>[**刷题小队**](https://raw.githubusercontent.com/tan45du/test/master/微信图片_20210320152235.2pthdebvh1c0.png)</u>进入。
|
||
|
||
#### [155. 最小栈](https://leetcode-cn.com/problems/min-stack/)
|
||
|
||
设计一个支持 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]
|
||
|
||
#### 题目解析
|
||
|
||
感觉这个题目的难度就在读懂题意上面，读懂之后就没有什么难的了，我们在上面的滑动窗口的最大值已经进行了详细描述，其实这个题目和那个题目思路一致。该题让我们设计一个栈，该栈具有的功能有，push，pop，top 等操作，并且能够返回栈的最小值。比如此时栈中的元素为 5，1，2，3。我们执行 getMin() ，则能够返回 1。这块是这个题目的精髓所在，见下图。
|
||
|
||
|
||
|
||
我们一起先通过一个视频先看一下具体解题思路，通过视频一定可以整懂的，我们注意观察栈 B 内的元素。
|
||
|
||
|
||
|
||
我们来对视频进行解析 1.我们执行入栈操作时，先观察需要入栈的元素是否小于栈 B 的栈顶元素，如果小于则两个栈都执行入栈操作。
|
||
|
||
2.栈 B 的栈顶元素则是栈 A 此时的最小值。则 getMin() 只需返回栈 B 的栈顶元素即可。
|
||
|
||
3.出栈时，需要进行对比，若栈 A 和栈 B 栈顶元素相同，则同时出栈，出栈好 B 的栈顶保存的仍为此时栈 A 的最小元素
|
||
|
||
#### 题目代码
|
||
|
||
```java
|
||
class MinStack {
|
||
//初始化
|
||
Stack<Integer> A,B;
|
||
public MinStack() {
|
||
A = new Stack<>();
|
||
B = new Stack<>();
|
||
}
|
||
//入栈，如果插入值，当前插入值小于栈顶元素，则入栈，栈顶元素保存的则为当前栈的最小元素
|
||
public void push(int x) {
|
||
A.push(x);
|
||
if (B.isEmpty() || B.peek() >= x) {
|
||
B.push(x);
|
||
}
|
||
|
||
}
|
||
//出栈，如果A出栈等于B栈顶元素，则说明此时栈内的最小元素改变了。
|
||
//这里需要使用 equals() 代替 == 因为 Stack 中存储的是 int 的包装类 Integer
|
||
public void pop() {
|
||
if (A.pop().equals(B.peek()) ) {
|
||
B.pop();
|
||
}
|
||
}
|
||
//A栈的栈顶元素
|
||
public int top() {
|
||
return A.peek();
|
||
}
|
||
//B栈的栈顶元素
|
||
public int getMin() {
|
||
return B.peek();
|
||
}
|
||
}
|
||
```
|
||
|
||
GO Code:
|
||
|
||
```go
|
||
type MinStack struct {
|
||
stack []int
|
||
minStk []int
|
||
}
|
||
|
||
/** initialize your data structure here. */
|
||
func Constructor() MinStack {
|
||
return MinStack{
|
||
stack: []int{},
|
||
minStk: []int{},
|
||
}
|
||
}
|
||
|
||
// Push 入栈，如果插入值，当前插入值小于栈顶元素，则入栈，栈顶元素保存的则为当前栈的最小元素
|
||
func (m *MinStack) Push(x int) {
|
||
m.stack = append(m.stack, x)
|
||
if len(m.minStk) == 0 || m.minStk[len(m.minStk) - 1] >= x {
|
||
m.minStk = append(m.minStk, x)
|
||
}
|
||
}
|
||
|
||
// Pop 出栈，如果stack出栈等于minStk栈顶元素，则说明此时栈内的最小元素改变了。
|
||
func (m *MinStack) Pop() {
|
||
temp := m.stack[len(m.stack) - 1]
|
||
m.stack = m.stack[: len(m.stack) - 1]
|
||
if temp == m.minStk[len(m.minStk) - 1] {
|
||
m.minStk = m.minStk[: len(m.minStk) - 1]
|
||
}
|
||
}
|
||
|
||
// Top stack的栈顶元素
|
||
func (m *MinStack) Top() int {
|
||
return m.stack[len(m.stack) - 1]
|
||
}
|
||
|
||
// GetMin minStk的栈顶元素
|
||
func (m *MinStack) GetMin() int {
|
||
return m.minStk[len(m.minStk) - 1]
|
||
}
|
||
```
|
||
|
||
###
|