最小栈

Java 欲哭无泪

您的代码已保存
运行超时:您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大。
case通过率为66.67%

可以用的方法都用了：

• 法1：
  一个栈记录差值：这个方法所有操作都是O(1)根本不需要格外的辅助空间

• 法2：
  使用一个辅助栈，记录最小值，所有操作也是O(1)

上述方法都使用过后，通过率都是66.67%
开始怀疑人生!
于是对第二种方法做了点点优化，通过数组手写一个栈（代码如下）

import java.util.*;
class MinStack{
    int[] array;
    int[] minArray;
    int index;
    public MinStack(int capacity){
        array=new int[capacity+5];
        minArray=new int[capacity+5];
        index=0;
        minArray[0]=Integer.MAX_VALUE;
    }
    public void push(int elem){
        array[++index]=elem;
        minArray[index]=Math.min(elem,minArray[index-1]);
    }
    public int pop(){
        index--;
        return array[index+1];
    }
    public int min(){
        return minArray[index];
    }
}
public class Main{
    public static void main(String[] args){
        MinStack minStack;
        int Q,op;
        Scanner in=new Scanner(System.in);
        Q=in.nextInt();
        minStack=new MinStack(Q);
        while(Q-->0){
            op=in.nextInt();
            if(op==0){
                System.out.println(minStack.min());
            }else if(op==1){
                minStack.push(in.nextInt());
            }else if(op==2){
                System.out.println(minStack.pop());
            }
        }
    }
}

没错，这次优化依旧没有什么*用，通过率还是66.67%
算了，思想了解了，不死磕！

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int q,op,x;
    cin>>q;
    stack<int>s1,s2;
    while(q--)
    {
        cin>>op;
        if(op==0)
            cout<<s2.top()<<endl;
        else if(op==1)
        {
            cin>>x;
            s1.push(x);
            if(s2.empty() || x <= s2.top()) 
                s2.push(x);
        }
        else if(op==2)
        {
            cout<<s1.top()<<endl;
            if(s1.top() == s2.top()) 
                s2.pop();
            s1.pop();
        }
    }
    return 0;
}

/*
空间换时间，另设一个栈b记录最小值
*/
#include <bits/stdc++.h>
using namespace std;
stack<int> a, b;
int main()
{
    //freopen("input.txt", "r", stdin);
    int t, op, x;
    cin >> t;
    while(t--) {
        scanf("%d", &op);
        if(op == 1) {
            scanf("%d", &x);
            a.push(x);
            if(!b.empty()) b.push(min(b.top(), x));
            else b.push(x);
        } else if (op == 2) {
            printf("%d\n", a.top());
            a.pop();
            b.pop();
        } else {
            printf("%d\n", b.top());
        }
    }
    return 0;
}

	

#include <bits/stdc++.h>
using namespace std;

int main(){
    int Q, op, x;
    cin>>Q;
    stack<int> S, S_min;
    while(Q--){
        cin>>op;
        if(op==0)
            cout<<S_min.top()<<endl;
        else if(op==1){
            cin>>x;
            S.push(x);
            if(S_min.empty() || x<=S_min.top())
                S_min.push(x);
        }else if(op==2){
            cout<<S.top()<<endl;
            if(S.top() == S_min.top())
                S_min.pop();
            S.pop();
        }
    }
    return 0;
}

#include <stdio.h>
#include <iostream>

using namespace std;

struct Stack {
	int *a;
	int *Min;
	int index;
	int mindex;
	Stack(int n) {
		a = new int [n + 1];
		Min = new int [n + 1];
		index = 0;
		mindex = 0;
		for (int i = 0; i < n; i++) {
			Min[i] = (int)1e9 + 10;
		}
	}
	~Stack() {
		delete []a;
		delete []Min;
	}
	void push(int val) {
		if (val <= Min[mindex]) {
			Min[++mindex] = val;
		}
		a[++index] = val;
	}
	int pop() {
		int temp = a[index];
		index--;
		if (temp == Min[mindex]) {
			mindex--;
		}
		return temp;
	}
	int query() {
		return Min[mindex];
	}
};

const int N = (int)5e5 + 10;

int main() {
	Stack st(N);
	int tt;
	scanf("%d", &tt);
	while (tt--) {
		int op;
		scanf("%d", &op);
		if (op == 1) {
			int val;
			scanf("%d", &val);
			st.push(val);
		} else if (op == 0) {
			printf("%d\n", st.query());
		} else {
			printf("%d\n", st.pop());
		}
	}
	return 0;
}

import java.util.Scanner;
import java.util.Stack;


class MinStack{
    // 最小栈，存入栈中的元素的一个数组，长度为2，一个是入栈的元素，另一个是之前入栈内的最小元素
    //数组栈, [当前值, 当前最小值]
    private Stack<int[]> stack = new Stack<>();
    // 构造方法
    public MinStack(){};

    // push方法
    public void push(int val){
        if(stack.isEmpty()){
            stack.push(new int[]{val, val});
        }else{
            stack.push(new int[]{val, Math.min(val, stack.peek()[1])});
        }
    }

    // pop方法
    public int pop(){
        return stack.pop()[0];
    }

    // getMin方法
    public int getMin(){
        return stack.peek()[1];
    }

}
// https://www.nowcoder.com/practice/a4d17eb2e9884359839f8ec559043761
public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int Q, op;
        Q = in.nextInt();
        MinStack minStack = new MinStack();
        for(int i = 0; i < Q; i++){
            op = in.nextInt();
            if(op == 0){
                System.out.println(minStack.getMin());
            }else if(op == 1){
                minStack.push(in.nextInt());
            }else if(op == 2){
                System.out.println(minStack.pop());
            }
        }
    }
}

#include<iostream>
#include<stack>
using namespace std;
class Solution{
public:
    int getmin(){
        return op2.top();
    }
    void push(int x){
        if(op1.empty()){
            op1.push(x);
            op2.push(x);
        }else{
            op1.push(x);
            if(x <= op2.top())
                op2.push(x);
        }
    }
    void pop(){
        if(!op1.empty()){
            int tmp = op1.top();
            if(tmp == op2.top())
                op2.pop();
            
            op1.pop();
            cout << tmp << endl;
        }
    }
private:
    stack<int> op1;
    stack<int> op2;
};
int main()
{
    Solution a;
    int x;
    cin >> x;
    while(x--){
        int op;
        cin >> op;
        if(op == 0){
            cout << a.getmin() << endl;
        }else if(op == 2){
            a.pop();
        }else if(op == 1){
            int t;
            cin >> t;
            a.push(t);
        }
    }
    return 0;
}

/*40%,在哪里会数组越界，求解答*/

import java.util.*;
class minStack{
    public Stack<Integer> stack = new Stack<Integer>();
    public Stack<Integer> min = new Stack<Integer>();
    public int minval = 0;
    public int pop(){
        int k = 0;
        if(!stack.isEmpty()){
            k=stack.pop();
            min.pop();
            minval = min.peek();
            return k;
        }
        else{
            return -1;
        }
    }
    public void push(int val){
        if(stack.isEmpty()){
            minval = val;
        }else{
            if(val<minval){
                minval = val;
            }
        }
        stack.push(val);
        min.push(minval);
    }
    public int getMin(){
        if(!stack.isEmpty()){
            return min.peek();
        }else{
            return -1;
        }
    }
}
public class Main{
    public static void main(String[] args){
        minStack mmm = new minStack();
        Scanner sc = new Scanner(System.in);
        int Q= sc.nextInt();
        int k = 0;
        int m = 0;
        for(int i = 0;i<Q;i++){
            sc.nextLine();
            k = sc.nextInt();
            if(k == 0){
                System.out.println(mmm.getMin());
            }
            if(k == 1){
                m = sc.nextInt();
                mmm.push(m);
            }
            if(k == 2){
                System.out.println(mmm.pop());
            }
        }
    }
}

class MyStack:
    def __init__(self):
        self.st_data = []
        self.st_min = []
    
    def push(self, node):
        self.st_data.append(node)
        if not self.st_min or node < self.st_min[-1]:
            self.st_min.append(node)
        else:
            self.st_min.append(self.st_min[-1])
    
    def pop(self):
        self.st_min.pop()
        return self.st_data.pop()
    
    def get_min(self):
        return self.st_min[-1]


st = MyStack()
Q = input()
for i in range(Q):
    #lst = input().split()
    #op = int(lst[0])
    op = raw_input()
    if op == "0":
        print(st.get_min())
    elif op == "2":
        print(st.pop())
    else:
        st.push(int(op[2:]))

#include <iostream>
#include <stack>
using namespace std;
stack<int> stack1,stack2;

void push(int value)
{
    stack1.push(value);
    if(stack2.empty())
        stack2.push(value);
    else if(value<=stack2.top())
        stack2.push(value);
}
int pop()
{
    if(stack1.top()==stack2.top())
        stack2.pop();
    int res=stack1.top();
    stack1.pop();
    return res;
}
int min()
{
    return stack2.top();
}
int main()
{
    int Q;
    cin >>Q;
    for(int i=0;i<Q;i++)
    {
        int op,x;
        cin>>op;
        if(op==0&& !stack1.empty())
            cout<<min()<<endl;
        if(op==1)
        {
            int x;
            cin >>x;
            push(x);
        }
        if(op==2&& !stack1.empty())
            cout<<pop()<<endl;
    }
    return 0;
}

#include<iostream>
#include<stack>
using namespace std;
class MinStack{
public:
    MinStack(){}
    void push(int value){
        _sss.push(value);
        if(_min.empty() || _min.top() > value)
            _min.push(value);
    }
    int pop(){
        if(_min.top() == _sss.top())
            _min.pop();
        int num =  _sss.top();
        _sss.pop();
        return num;
    }
    int min(){
        return _min.top();
    }
private:
    stack<int> _sss;
    stack<int> _min;
};
int main(){
    int Q = 0;
    MinStack s;
    cin >> Q;
    for(int i = 0;i < Q;++i){
        int op = 0;
        cin >> op;
		if (op == 0) {
			cout << s.min() << endl;
		}
		else if (op == 1)
		{
            int op2 = 0;
            cin >> op2;
			s.push(op2);
		}
		else if (op == 2)
		{
			cout << s.pop() << endl;
		}
	}
    return 0;
}