这是我在 HackerRank 上研究此问题的解决方案时遇到的问题。它基本上归结为以下内容：给定一个数组 A 和一个整数 K，问题要求您找到大小为 K 的 A 的每个连续子数组的最大值。还有一些额外的东西（对于每个测试用例，这个问题发生 T次，并且必须从输入中读取才能获得 A)，但这就是它的要点。
该站点会检查您的答案是否足够有效，即使您的代码最终产生了正确的输出，提交也可能由于超时而失败。现在，当您第一次进入代码区域时，有一些预定义的代码供您使用：
#include <iostream>
#include <deque>
using namespace std;
void printKMax(int arr[], int n, int k){
//Write your code here.
}
int main(){
int t;
cin >> t;
while(t>0) {
int n,k;
cin >> n >> k;
int i;
int arr[n];
for(i=0;i<n;i++)
cin >> arr[i];
printKMax(arr, n, k);
t--;
}
return 0;
}
一切都很好，该网站已经为您的利益处理了输入，并为您指明了模块化方法。您所要做的实际上是解决连续子数组问题；我使用以下函数完成了它，它通过了所有测试用例：
void printKMax(int arr[], int n, int k){
// Queue will store up to k elements (moving window)
// Elements stored will be indices of the array. Indices allow to compare with loop iterator for removal of oldest element as window moves
// Most recent elements are pushed to the back (so they take longer to be popped)
std::deque<int> Q(k);
// Iterate over the first window
int i;
for (i = 0; i < k; ++i) {
// A new element (arr[i]) to be added at the back invalidates all elements added before it that are no greater (if they are smaller, they cannot be a maximum; if they are equal, the new element is more recent). Those elements are popped
// This guarantees that the values corresponding to Q's indices will be increasing (strictly) from back to front. In particular, the front will be the maximum
while ((!Q.empty()) && arr[i] >= arr[Q.back()])
Q.pop_back();
Q.push_back(i);
}
// Iterate, letting the window move
for (; i < n; ++i) {
// Print the largest element (window has not moved yet), followed by a space
cout << arr[Q.front()] << " ";
// Use indices to determine if oldest element has gone out of the window
if (Q.front() <= i - k) Q.pop_front();
// Add new element, like before
while ((!Q.empty()) && arr[i] >= arr[Q.back()])
Q.pop_back();
Q.push_back(i);
}
// Print the maximum element of last window, and end the line
cout << arr[Q.front()] << endl;
}
然而，回想起来，我认为我可以（稍微？）做得更好。对于每个测试用例，main 中的输入处理循环 n 次以填充数组 arr，然后 printKMax 也依次循环 n 次以创建和滑动移动窗口。我想我可以将它们组合成一个循环，我想这应该更有效。我用下面的代码做到了，这和以前基本相同，但是将 printKMax 合并到了 main.js 中。这次我将省略评论。
int main(){
int t;
cin >> t;
while(t>0) {
int i = 0, n, k;
cin >> n >> k;
int arr[n];
std::deque<int> Q(k);
for (; i < k; ++i) {
cin >> arr[i];
while ((!Q.empty()) && arr[i] >= arr[Q.back()])
Q.pop_back();
Q.push_back(i);
}
for (; i < n; ++i) {
cout << arr[Q.front()] << " ";
if (Q.front() <= i - k) Q.pop_front();
cin >> arr[i];
while ((!Q.empty()) && arr[i] >= arr[Q.back()])
Q.pop_back();
Q.push_back(i);
}
cout << arr[Q.front()] << endl;
t--;
}
return 0;
}
然而，这一次，除了最简单的测试用例之外，代码都失败了，在每种情况下，由于时间限制。
我知道在实践中模块化是好的，但在这一点上，我的兴趣比其他任何事情都更“学术”。关于实际程序，我是否缺少某些东西，或者这与我不知道的幕后运行方式有关？
编辑：正如 PaulMcKenzie 所建议的，我使用 g++ 来运行程序的两个版本，使用失败的测试用例之一作为输入。两者都运行良好并产生了相同的输出，但一个printKMax运行了 3.97 秒，而一个没有运行了 5.44 秒。大约需要 37% 的时间。