这是我研究this problem on 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;
}
但是，回头看，我以为我可以做得（稍微好一点？）。对于每个测试用例，主处理中的输入循环n次以填充数组arr，然后printKMax依次循环n次以创建并滑动移动窗口。我以为可以将它们组合成一个循环，我想它应该更有效。我使用以下代码完成了此操作，该代码与以前基本相同，但printKMax并入了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;
}
然而，这是代码，除了最简单的测试用例之外，由于时间限制，在每种情况下都如此。我了解实践中模块化是失败
good
，但是在这一点上，我的兴趣比其他任何事情都更加“学术”。我在实际程序中缺少什么，还是与我不知道的幕后运行方式有关？这是我在HackerRank上研究此问题的解决方案时遇到的问题。基本上可以归结为以下几点：给定一个数组A和一个整数K，问题将要求您找到最大值...