来老铁干了这碗代码 2020-02-19 17:27 采纳率: 100%
浏览 686
已采纳

一道关于栈的水题,无法降低时间复杂度。求帮忙!谢谢!

图片说明图片说明图片说明

别看这道题水了吧唧, 但作者只给了600ms的运行时间,
第一重循环肯定是N--,
但找最小值的操作,用输入一次判断一次的方法行不通, 因为他会有弹出的操作,当保存最小值时,如果弹出的是该值, 那么我们找不到第二小的。
因此就只能遍历,但这样时间复杂度就变成了n²,一定运行超时。我真的想不到更简化的方法了,各清位大佬们支支招。谢谢!

非满分代码:

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std ;

int main()
{
    ios::sync_with_stdio(false);
    int n, x;
    cin >> n;
    string a;                                                    
    vector<int>v;
    bool flag = false;
    while(n--) {    
        cin >> a;
        if(a[1] == 'u') { cin >> x; v.push_back(x); }
        else if(a[1] == 'o') v.pop_back(); 
        else  {
            int minValue = *min_element(v.begin(),v.end());         //最小范围的定义数。 
            cout << minValue << endl;
        } 
    }
    return 0;
}

###运行结果:

  • 写回答

2条回答 默认 最新

  • ALTaleX 2020-02-19 18:17
    关注

    本人也是个菜鸟
    由于数据范围没有给全,以下代码仅供参考,没有用C++的东西

    #include <stdio.h>
    int num[1000000];
    int tot = 0, min, pos;
    int getmin() {
        int min = num[0];
        int i;
        for(i = 0; i < tot; i++) {
            if(num[i] < min) {
                min = num[i];
            }
        }
        return min;
    }
    int main() {
        int n, i;
        scanf("%d", &n);
        char op[3];
        for(i = 0; i < n; i++) {
            scanf("%s", &op);
            if(op[1] == 'u') {
                scanf("%d", &num[tot]);
                if(tot) {
                    if(min > num[tot]) {
                        min = num[tot];
                        pos = tot;
                    }
                } else {
                    min = num[tot];
                    pos = tot;
                }
                tot++;
                continue;
            }
            if(op[1] == 'o') {
                tot--;
                num[tot] = 0;
                min = getmin();
                continue;
            }
            if(op[1] = 'i') {
                printf("%d\n", min);
                continue;
            }
        }
        return 0;
    }
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

悬赏问题

  • ¥50 树莓派安卓APK系统签名
  • ¥15 maple软件,用solve求反函数出现rootof,怎么办?
  • ¥65 汇编语言除法溢出问题
  • ¥15 Visual Studio问题
  • ¥20 求一个html代码,有偿
  • ¥100 关于使用MATLAB中copularnd函数的问题
  • ¥20 在虚拟机的pycharm上
  • ¥15 jupyterthemes 设置完毕后没有效果
  • ¥15 matlab图像高斯低通滤波
  • ¥15 针对曲面部件的制孔路径规划,大家有什么思路吗