在尝试从HackerRank解决这个问题时,我编写了以下代码,该代码通过了22/27测试用例。不幸的是,我无法访问它失败的测试用例。
问题
你有一个空序列,你将得到 N 个查询。每个查询都是以下三种类型之一:
1 x => 将元素 x 推入堆栈。
2 => 删除堆栈顶部的元素。
3 => 打印堆栈中的最大元素。
输入格式
输入的第一行包含一个整数 N。接下来的 N 行分别包含上述查询。(保证每个查询都有效)
约束
1 <= N <= 10^5
1 <= x <= 10^9
1 <= type <= 3
输出格式
对于每个类型 3 查询,在新行上打印堆栈中的最大元素。
示例输入
10 1 97 2 1 20 21 26
1 20
2
3
1 91 3
示例输出
26
91
我解决这个问题的方法是——
- 使用一个向量来保存堆栈的状态
- 使用另一个向量保存输入的最大值
我的解决方案如下——
#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;
}
有人可以帮我找出我在代码中遗漏的错误或极端情况,以便我可以修复它并通过所有测试用例吗?
问题是你只在 x> mymax.back() 时才添加到 mymax。所以,如果 x == mymax.back(),你什么都不做。现在想象一下,将 1、3、3、3、3、3 插入到堆栈中。在这种情况下,您的"mymax"只有一个 3,一旦"删除"类型的查询到达,您的最大值将变为 1;然而,真正的答案是3。解决此问题将为您提供正确的答案。
但是,对于这样的问题,我通常在 c++ 中使用"多集"数据结构。插入堆栈的任何内容也会插入到多集(删除也是如此)。但是,多集可以更新O(logn)时间。它可以报告 O(1) 中的最大元素。
由于 N <= 10^5。该算法的复杂性将是O(N log N),这仍然非常合理。
请注意,multiset 与集合数据结构非常相似,不同之处在于您可以有重复的数字,这在您的问题中非常有用。
这是一个很酷的python解决方案,你只需要使用两个堆栈。
import sys
if __name__ == "__main__":
stack = []
stack_for_max = [-sys.maxsize]
for i in range(0, int(input())):
data = str(input())
if " " in data:
data_to_be_added = int(data.split(" ")[1])
stack.append(data_to_be_added)
if data_to_be_added >= stack_for_max[-1]:
stack_for_max.append(data_to_be_added)
elif data == "2":
top_of_the_stack = stack.pop()
if top_of_the_stack == stack_for_max[-1]:
stack_for_max.pop()
else:
print(stack_for_max[-1])