weixin_43899069
2020-02-19 17:27 阅读 673

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

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

别看这道题水了吧唧, 但作者只给了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条回答 默认 最新

  • 已采纳
    weixin_43820461 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;
    }
    
    点赞 2 评论 复制链接分享
  • JonathanYan JonathanYan 2020-02-19 22:05

    用最小堆来做,栈里存储值的同时存储其在最小堆里的位置,弹出的时候将堆末元素和该元素互换然后维护堆结构。
    弹出和插入过程由于每次堆基本有序,复杂度在O(n)。
    堆用结构体数组模拟,val是正常栈压入的值,left,right对应其在最小堆中的关系

    struct node{
        node *left, *right;
            int val;
    }
    

    20号有空再给你写程序。另外请附题目出处连接,我去测试程序

    点赞 1 评论 复制链接分享

相关推荐