牛客网刷题-设计getMin功能的栈问题描述示例解决思路代码实现

96 阅读 0 评论 64 点赞

我是靠谱客的博主喜悦电脑，这篇文章主要介绍牛客网刷题-设计getMin功能的栈问题描述示例解决思路代码实现，现在分享给大家，希望可以做个参考。

问题描述

实现一个特殊功能的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。
有三种操作种类，op1表示push，op2表示pop，op3表示getMin。你需要返回和op3出现次数一样多的数组，表示每次getMin的答案

1<=操作总数<=1000000
-1000000<=每个操作数<=1000000
数据保证没有不合法的操作

输入描述:
输入一个二维数组

输出描述:
输出一个一维数组（当前栈的最小元素）

示例

示例1

输入
[[1,3],[1,2],[1,1],[3],[2],[3]]

输出
[1,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
27
28
29
30
31
32
33
34
// 思路1
public class Solution {
public int[] getMinStack(int[][] op) {
// write code here
Stack<Integer> stack1 = new Stack<>(); // 记录完整的放入栈数据
Stack<Integer> stack2 = new Stack<>(); // 记录到目前放入为止的元素里最小的数字
List<Integer> list = new ArrayList<>();
for (int i = 0; i < op.length; i++) {
if (op[i][0] == 3) {
// 获取stack2栈顶的元素
list.add(stack2.peek());
} else if (op[i][0] == 2) {
// 弹出栈顶
int temp = stack1.pop();
// 如果弹出的元素是最小元素，stack2也弹出
if (temp == stack2.peek())
stack2.pop();
} else {
int temp = op[i][1];
// 压栈
stack1.push(temp);
// 如果压栈元素小于stack2的栈顶元素，则压栈
if (stack2.isEmpty() || temp <= stack2.peek())
stack2.push(temp);
}
}
int[] res = new int[list.size()];
for (int i = 0; i < list.size(); i++) {
res[i] = list.get(i);
}
return res;
}
}