Skip to content

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();
        }
    }
}