实现一个特殊功能的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。
每次输入 [1,*] 时，表示向栈中加入数字 * ，[2] 表示移除栈顶元素，[3] 表示输入栈中最小元素，添加最小元素到结果集中即可。
数据范围：操作数 
要求：各操作的时间复杂度 )
，空间复杂度 )
[编程题]设计getMin功能的栈
- 热度指数：15577 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
- 算法知识视频讲解
示例1
输入
[[1,3],[1,2],[1,1],[3],[2],[3]]
输出
[1,2]
说明
操作分别是：向栈push3，向栈push2，向栈push1，此时从栈底到栈顶是[3,2,1]。获得最小值，此时是1。栈pop操作，此时栈底到栈顶是[3,2]。获得最小值，此时是2。
备注:
有三种操作种类，op1表示push，op2表示pop，op3表示getMin。你需要返回和op3出现次数一样多的数组，表示每次getMin的答案1<=操作总数<=1000000
-1000000<=每个操作数<=1000000
数据保证没有不合法的操作
import java.util.*;
class MinStack<T extends Comparable>{
private Stack<T> stack = new Stack<>();
private Stack<T> minStack = new Stack<>();
public void push(T item){
stack.push(item);
if(minStack.isEmpty()){
minStack.push(item);
}else if(minStack.peek().compareTo(item)>0){
minStack.push(item);
}else{
minStack.push(minStack.peek());
}
}
public T pop(){
minStack.pop();
return stack.pop();
}
public T min(){
return minStack.peek();
}
}
public class Solution {
/**
* return a array which include all ans for op3
* @param op int整型二维数组 operator
* @return int整型一维数组
*/
public int[] getMinStack (int[][] op) {
if(op==null||op.length==0){
return new int[0];
}
List<Integer> res = new ArrayList<>();
MinStack<Integer> stack = new MinStack();
for(int i=0,len=op.length;i<len;++i){
int[] tmp = op[i];
if(tmp[0]==1){
stack.push(tmp[1]);
}else if(tmp[0]==2){
stack.pop();
}else if(tmp[0]==3){
res.add(stack.min());
}
}
return res.stream().mapToInt(Integer::intValue).toArray();
}
}
发表于 2021-06-04 08:24:57
回复(0)
题目意思：[1,x]表示入栈x [2]表示出栈 [3]表示getmin
解答：建立一个堆栈min和一个动态数组队列sz,堆栈中每当压入的数大于栈顶的数，保留这个数，否则将栈顶数复制，（这样保证了堆栈顶一直存放的是最小数，而且不会将之前的数的个数改变，因此当pop时，能够保证之前的最小数）
import java.util.*;
import java.lang.*;
//ArrayList基于数组实现，是一个动态的数组队列。但是它和Java中的数组又不一样，它的容量可以自动增长
public class Solution {
public int[] getMinStack (int[][] op) {
Stack<Integer> min=new Stack<Integer>();
ArrayList<Integer> sz=new ArrayList<>();
min.push(Integer.MAX_VALUE);
for(int i=0;i<op.length;i++)
{
if(op[i][0]==1){
min.push(Math.min(op[i][1],min.peek()));
}
else if(op[i][0]==2){
min.pop();
}
else{
sz.add(min.peek());
}
}
int[] result=new int[sz.size()];
for(int i=0;i<sz.size();i++){
result[i]=sz.get(i);
}
return result;
}
}
发表于 2021-03-23 21:44:33
回复(1)
class MinStack{
Deque<Integer> stackA ,stackB;
public MinStack(){
stackA = new ArrayDeque<>();
stackB = new ArrayDeque<>();
}
public void push(int x){
//如果stackA 和stackB 同步插入 如果发现当前值比最小栈B 的peek小 那么插入当前元素 否则peek元素再插一遍
stackA.push(x);
stackB.push(Math.min(x,stackB.peek()==null?1000001:stackB.peek()));
}
public void pop(){
stackB.pop();
stackA.pop();
}
public int min(){
return stackB.peek();
}
}
public int[] getMinStack (int[][] op) {
// write code here
MinStack minStack = new MinStack();
int[] res = new int[1000000];
//输出结果的个数
int count =0;
for (int i = 0; i < op.length; i++) {
if (op[i][0]==1){
//push
minStack.push(op[i][1]);
}else if (op[i][0]==2){
//pop
minStack.pop();
}else if (op[i][0]==3){
//min
res[count++] = minStack.min();
}
}
return Arrays.copyOfRange(res,0,count);
}
发表于 2021-03-12 08:08:26
回复(0)
public int[] getMinStack (int[][] op) {
// write code here
Stack<Integer> s1=new Stack<>();
Stack<Integer> s2=new Stack<>();
ArrayList<Integer> list=new ArrayList<>();
for(int i=0;i<op.length;i++){
int choice=op[i][0];
if(choice==1){
int val=op[i][1];
s1.push(val);
if(s2.isEmpty()||(!s2.isEmpty()&&val<s2.peek())){
s2.push(val);
}
}else if(choice==2&&!s1.isEmpty()){
int val=s1.pop();
if(val==s2.peek()){
s2.pop();
}
}else{
list.add(s2.peek());
}
}
int[] res=new int[list.size()];
for(int i=0;i<res.length;i++){
res[i]=list.get(i);
}
return res;
}
编辑于 2021-03-13 20:27:28
回复(0)
import java.util.*;
public class Solution {
Stack<Integer> stack1 = new Stack();
Stack<Integer> minStack = new Stack();
/**
* [[1,3],[1,2],[1,1],[3],[2],[3]]
* 有三种操作种类，op1表示push，op2表示pop，op3表示getMin。你需要返回和op3出现次数一样多的数组，表示每次getMin的答案
* 麻蛋 [1]代表push [2]代表pop [3]表示getMin操作 [1,3]中1代表先push 2代表要push的值
* [1,2]代表push然后pop
*/
/**
* 思路：建立两个栈，一个data栈压入数据（和正常的压栈一样），
* 另一个min栈压入最小值。如果压入的数据比当前最小值小则压入min栈，
* 大于当前最小值则重复压入当前min栈栈顶元素。 min栈和data保持同步的入栈出栈操作，
* 这样始终保持min栈栈顶元素为最小值。
*/
public int[] getMinStack (int[][] op) {
List<Integer> list = new ArrayList();
for(int[] opt : op){
//代表PUSH
if(opt[0] == 1){
push(opt[1]);
}else if(opt[0] == 2){//代表pop
pop();
}else{//代表getMin
list.add(getMin());
}
}
int[] result = new int[list.size()];
for(int i=0;i<list.size();i++){
result[i] = list.get(i);
}
return result;
}
public void push(int val){
if(minStack.isEmpty()){
minStack.push(val);
}else if(val <= getMin()){
minStack.push(val);
}
stack1.push(val);
}
public void pop(){
if(stack1.isEmpty() || minStack.isEmpty()){
return;
}
//peek()不弹出 只返回栈顶元素 注意这里要用equals 因为是Integer 如果用== 将会不相等
if(stack1.peek().equals(minStack.peek()) ){
minStack.pop();
}
stack1.pop();
}
public int getMin(){
return minStack.peek();
}
}
发表于 2021-01-20 23:24:51
回复(0)
import java.util.*;
public class Solution {
/**
* return a array which include all ans for op3
* @param op int整型二维数组 operator
* @return int整型一维数组
*/
public int[] getMinStack (int[][] op) {
ArrayList<Integer> result = new ArrayList<Integer>();
Stack<Integer> stack = new Stack<Integer>();
ArrayList<Integer> arr = new ArrayList<Integer>();
for (int[] o: op){
if (o[0]==1){
stack.push(o[1]);
arr.add(o[1]);
}else if(o[0]==2)arr.remove(stack.pop());
else if (o[0]==3) result.add(Collections.min(arr));
}
return result.stream().mapToInt(Integer::intValue).toArray();
}
}
public class Solution {
/**
* return a array which include all ans for op3
* @param op int整型二维数组 operator
* @return int整型一维数组
*/
public int[] getMinStack (int[][] op) {
ArrayList<Integer> result = new ArrayList<Integer>();
Stack<Integer> stack = new Stack<Integer>();
ArrayList<Integer> arr = new ArrayList<Integer>();
for (int[] o: op){
if (o[0]==1){
stack.push(o[1]);
arr.add(o[1]);
}else if(o[0]==2)arr.remove(stack.pop());
else if (o[0]==3) result.add(Collections.min(arr));
}
return result.stream().mapToInt(Integer::intValue).toArray();
}
}
发表于 2020-12-19 13:41:07
回复(0)
栈用来存储，用一个treeset来排序，调用first()获取最小值
import java.util.*;
public class Solution {
/**
* return a array which include all ans for op3
* @param op int整型二维数组 operator
* @return int整型一维数组
*/
public int[] getMinStack (int[][] op) {
// write code here
if(op.length<0){
throw new RuntimeException("xxx");
}
List<Object> list = new ArrayList<>();
Stack<Integer> stack = new Stack();
TreeSet set = new TreeSet();
for(int[] oop:op){
if(oop[0]==1){
stack.push(oop[1]);
set.add(oop[1]);
}else if(oop[0]==2){
Integer i = stack.pop();
set.remove(i);
}else{
list.add(set.first());
}
}
int[] result = new int[list.size()];
for(int i=0;i<list.size();i++){
result[i] = Integer.valueOf(String.valueOf(list.get(i)));
}
return result;
}
}
发表于 2020-12-18 16:59:18
回复(0)
额外维护一个单调栈：
import java.util.*;
public class Solution {
private Deque<Integer> stack = new ArrayDeque<>();
private Deque<Integer> sortedStack = new ArrayDeque<>();
/**
* return a array which include all ans for op3
* @param op int整型二维数组 operator
* @return int整型一维数组
*/
public int[] getMinStack (int[][] op) {
// write code here
if(op == null || op.length == 0){ return new int[0]; }
int len = op.length;
List<Integer> list = new ArrayList<>(10);
for(int[] o : op){
switch(o[0]){
case 1: {this.pushOp(o[1]);break;}
case 2: {this.popOp();break;}
case 3: {list.add(this.getMin());break;}
default:break;
}
}
int[] res = new int[list.size()];
for(int i = 0; i < res.length; ++i){
res[i] = list.get(i);
}
return res;
}
private void pushOp(int num){
stack.push(num);
if(!sortedStack.isEmpty()){
int top = sortedStack.peek();
if(num > top){ return; }
}
sortedStack.push(num);
}
private void popOp(){
if(!stack.isEmpty()){
int top = stack.pop();
if(sortedStack.peek() == top){
sortedStack.pop();
}
}
}
private int getMin(){
if(!sortedStack.isEmpty()){
return sortedStack.peek();
}
return -1;
}
}
发表于 2020-11-13 10:52:40
回复(0)
import java.util.*;
public class Solution {
Node stack = null;
Node min = null;
Node pre = null;
/**
* return a array which include all ans for op3
* @param op int整型二维数组 operator
* @return int整型一维数组
*/
public int[] getMinStack (int[][] op) {
// write code here
LinkedList<Integer> list = new LinkedList<>();
for (int[] a : op) {
if (a.length > 1) {
push(a[1]);
} else {
if (a[0] == 2) {
pop();
} else {
list.add(getMin());
}
}
}
int[] res = new int[list.size()];
for (int i = 0; i < list.size(); i ++) {
res[i] = list.get(i);
}
return res;
}
public void push(int val) { //O(1),O(1)
Node node = new Node(val);
node.next = stack;
stack = node;
if (min == null || min.val > val) {
min = stack;
pre = null;
} else {
if (min == stack.next) {
pre = stack;
}
}
}
public int pop() { // 最好O(1)，O(1).最坏O(n),O(1)
int res = stack.val;
if (min == stack) { //重新找个最小值
min = null;
Node p = stack.next;
Node t = null;
while (p != null) {
if (min == null || min.val > p.val) {
min = p;
pre = t;
}
t = p;
p = p.next;
}
} else if (min == stack.next) {
pre = null;
}
Node t = stack.next;
stack.next = null;
stack = t;
return res;
}
public int getMin() { //O(1),O(1)
return min.val;
}
class Node {
int val;
Node next;
public Node (int val) {
this.val = val;
}
}
public class Solution {
Node stack = null;
Node min = null;
Node pre = null;
/**
* return a array which include all ans for op3
* @param op int整型二维数组 operator
* @return int整型一维数组
*/
public int[] getMinStack (int[][] op) {
// write code here
LinkedList<Integer> list = new LinkedList<>();
for (int[] a : op) {
if (a.length > 1) {
push(a[1]);
} else {
if (a[0] == 2) {
pop();
} else {
list.add(getMin());
}
}
}
int[] res = new int[list.size()];
for (int i = 0; i < list.size(); i ++) {
res[i] = list.get(i);
}
return res;
}
public void push(int val) { //O(1),O(1)
Node node = new Node(val);
node.next = stack;
stack = node;
if (min == null || min.val > val) {
min = stack;
pre = null;
} else {
if (min == stack.next) {
pre = stack;
}
}
}
public int pop() { // 最好O(1)，O(1).最坏O(n),O(1)
int res = stack.val;
if (min == stack) { //重新找个最小值
min = null;
Node p = stack.next;
Node t = null;
while (p != null) {
if (min == null || min.val > p.val) {
min = p;
pre = t;
}
t = p;
p = p.next;
}
} else if (min == stack.next) {
pre = null;
}
Node t = stack.next;
stack.next = null;
stack = t;
return res;
}
public int getMin() { //O(1),O(1)
return min.val;
}
class Node {
int val;
Node next;
public Node (int val) {
this.val = val;
}
}
}
大家帮忙看看这个代码吧，为什么会超时，我感觉只有pop()操作的时间复杂度能达到O(n)。其他的都为O(1)。这种时间复杂度的实现都不能通过吗？
发表于 2020-09-09 10:07:11
回复(1)
public class Solution {
/**
* return a array which include all ans for op3
* @param op int整型二维数组 operator
* @return int整型一维数组
*/
public int[] getMinStack (int[][] op) {
// write code here
Stack<Integer> stack = new Stack<>();
//List<Integer> ans = new ArrayList<>();
int count = 0;
for(int[] o : op){ // 统计有多少个opt3,用于初始化ans数组
if(o[0] == 3)
count++;
}
int[] ans = new int[count];
count = 0;
int min = -1;
for(int[] o : op){
switch (o[0]){
case 1:
if(stack.isEmpty()){// 栈空，差值0入栈，min=当前值
stack.push(0);
min = o[1];
}
else{
int d = o[1] - min; // 计算与最小值的差值
stack.push(d);
min = d > 0 ? min : o[1]; //如果差值大于0，非最小值
}
break;
case 2:
int d = stack.pop();
if(d < 0){ // 栈顶元素与最小值差值小于0，出栈的为当前最小值，更新最小值
min -= d;
}
break;
case 3:
//ans.add(min);
ans[count++] = min;
break;
}
}
//int[] ansa = new int[ans.size()];
//for (int i = 0; i < ans.size(); i++) {
//ansa[i] = ans.get(i);
// }
return ans;
}
}
发表于 2020-09-05 20:31:05
回复(0)
public int[] getMinStack (int[][] op) {
// write code here
int min = 0;
Stack<Integer> stack = new Stack<Integer>();
ArrayList<Integer> list = new ArrayList<Integer>();
for(int[] opt: op) {
int first = opt[0];
if(first == 1) { //push
if(stack.empty()) {
min = opt[1];
stack.push(min);
}
else {
if(opt[1] < min) {
stack.push(2*opt[1]-min);
min = opt[1];
}
else {
stack.push(opt[1]);
}
}
}
else if(first == 2) { //pop
if(stack.empty()) {
return new int[0];
}
int n = stack.pop();
if(n < min) {
min = 2*min - n;
}
}
else { //getMin
list.add(min);
}
}
int[] ans = new int[list.size()];
for(int i=0; i<ans.length; i++) {
ans[i] = list.get(i);
}
return ans;
}
发表于 2020-08-29 03:42:30
回复(0)
问题信息
难度：
11条回答
91收藏
4745浏览
通过挑战的用户
-
2023-02-05 13:43:40 -
2023-01-16 15:59:49
-
2022-12-13 16:03:31 -
2022-11-27 12:02:03 -
2022-11-14 14:17:29
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
