问题描述

实现一个特殊功能的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。
有三种操作种类，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. 通过两个栈解决，一个栈存储压栈的元素，另一个栈存储到目前为止压栈元素最小元素（大小依次压栈）

方法

1. 通过两个栈解决，一个栈存储压栈的元素，另一个栈存储到目前为止压栈元素最小元素（大小依次压栈）

代码实现

// 思路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;
}
}

时间复杂度分析：
O(M)：遍历数组

空间复杂度分析：
O(N)：使用了两个额外的栈，栈的最大存储为n。

小伙伴如果想测试的话，可以直接到牛客网这个链接做测试

设计getMin功能的栈-牛客网

最后

以上就是喜悦电脑最近收集整理的关于牛客网刷题-设计getMin功能的栈问题描述示例解决思路代码实现的全部内容，更多相关牛客网刷题-设计getMin功能内容请搜索靠谱客的其他文章。