14370: 【原4370】Min Stack

题目

题目描述

author: Mars 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4370

Description

设计并实现一个新的栈类，支持O(1)时间复杂度的push，pop，top，getMin操作：

• push(x)——x 入栈；
• pop()——堆顶元素出栈；
• top()——返回栈顶元素
• getMin()——求栈内最小值

Input Format

第1行：一个整数n表示共n条指令；
第2至n+1行：每行一条指令op，分为以下4中情况：

• 0 x : push(x)
• 1 : pop()
• 2 : top()
• 3 : getMin()

Output Format

对于op为2或3的情况，每行输出操作返回的整数；
若op为1、2或3时栈空，输出“Empty”（不带引号）

Sample Input

10
0 1
0 2
2
3
1
3
1
1
2
3

Sample Output

2
1
1
Empty
Empty
Empty

Limits:

0 < n <= 10^6
0 <= x < 3 * 10^9

ligongzzz's solution

#include <iostream>
#include <stack>
using namespace std;

class myStack {
    stack<unsigned  int> real_stack;
    stack<pair<unsigned int,unsigned int>> min_stack;

public:
    void push(unsigned int x) {
        real_stack.push(x);
        if (min_stack.empty()||min_stack.top().second>x){
            min_stack.push(make_pair(real_stack.size(), x));
        }
    }

    void pop() {
        if (real_stack.empty()) {
            cout << "Empty\n";
            return;
        }
        if (min_stack.top().first==real_stack.size()) {
            min_stack.pop();
        }
        real_stack.pop();
    }

    void top() {
        if (real_stack.empty()) {
            cout << "Empty\n";
            return;
        }
        cout << real_stack.top() << "\n";
    }

    void getMin() {
        if (real_stack.empty()) {
            cout << "Empty\n";
            return;
        }
        cout << min_stack.top().second << "\n";
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n = 0;
    cin >> n;

    myStack stack1;

    for (;n;--n) {
        int a;
        cin >> a;
        if (a==0) {
            unsigned int b;
            cin >> b;
            stack1.push(b);
        }
        else if (a==1) {
            stack1.pop();
        }
        else if (a==2) {
            stack1.top();
        }
        else {
            stack1.getMin();
        }
    }
}