c++ - 在恒定时间内找到堆栈中的最大元素

Question

试图从 HackerRank 解决这个问题时，我编写了以下通过 22/27 测试用例的代码。不幸的是，我无法访问失败的测试用例。

问题

你有一个空序列，你将得到 N 个查询。每个查询都是以下三种类型之一:

1 x => Push the element x into the stack.
2 => Delete the element present at the top of the stack.
3 => Print the maximum element in the stack.

输入格式
输入的第一行包含一个整数 N。接下来的 N 行每行包含一个上述查询。 (保证每次查询有效)

约束
1 <= N <= 10^5
1 <= x <= 10^9
1 <= type <= 3

输出格式
对于每种 3 查询，在新行上打印堆栈中的最大元素。

示例输入

10
1 97
2
1 20
2
1 26
1 20
2
3
1 91
3

示例输出

26
91

我解决这个问题的方法是-

1. 用一个 vector 来保存栈的状态
2. 使用另一个 vector 来保存输入的最大值
   

我的解决方案如下 -

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

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    vector<int> myvect;        /* Vector to hold the inputs */
    vector<int> mymax;         /* Vector to hold max elements */
    unsigned times;
    unsigned type;
    unsigned x;
    cin >> times;
    if (times <= 100000) {
        for (unsigned i = 0; i < times; i++) {
            cin >> type;
            if (type >= 1 && type <= 3) {
                switch (type) {
                    case 1:
                        cin >> x;
                        if (x <= 1000000000) {
                            myvect.push_back(x);
                            if (mymax.empty())
                                mymax.push_back(x);
                            else if (x > mymax.back())
                                    mymax.push_back(x);
                        }
                        break;
                    case 2:
                        if (!myvect.empty()) {
                            if (!mymax.empty() && (myvect.back() == mymax.back()))
                                mymax.pop_back();
                            myvect.pop_back();
                        }
                        break;
                    case 3:
                        cout << mymax.back() << endl;
                        break;
                    default:
                        cout << "We should not get in here" << endl;
                }
            }
        }
    }
    return 0;
}

有人可以帮我找出我在代码中遗漏的错误或极端情况，以便我修复它并通过所有测试用例吗？

Answer 1

问题是只有当 x > mymax.back() 时你才添加到 mymax。所以，如果 x == mymax.back() 你什么都不做。现在想象一下，将 1、3、3、3、3 插入到堆栈中。在这种情况下，您的“mymax”只有一个 3，一旦“delete”类型的查询到达，您的 max 将变为 1；然而，真正的答案是 3。解决这个问题会给你正确的答案。

但是，对于此类问题，我通常使用 C++ 中的“多重集”数据结构。插入到堆栈中的任何内容也将插入到多重集中(删除也是如此)。但是，multiset 可以在 O(logn) 时间内更新。并且它可以报告 O(1) 中的最大元素。

因为 N <= 10^5。这个算法的复杂度会是O(N log N)，还是很合理的。

请注意，multiset 与集合数据结构非常相似，不同之处在于您可以使用重复 数字，这在您的问题中非常有用。