是我的队列实现写错了吗?还是哪里有问题?用STL就过了,但是我看了下,我的队列好像是没问题的。。。
#include <iostream>
#include <algorithm>
using namespace std;
class Queue {
private:
int *queue;
int frontIndex = 0;
int backIndex = 0;
public:
Queue(int size) {
this->size = size;
this->queue = new int[size];
}
~Queue() {
delete[] queue;
}
int front() {
return this->queue[frontIndex];
}
int back() {
return this->queue[(backIndex - 1 + size) % size];
}
bool empty() {
return length == 0;
}
bool pop_front() {
if (length == 0) { return false; }
frontIndex = (frontIndex + 1) % size;
length -= 1;
return true;
}
bool pop_back() {
if (length == 0) { return false; }
backIndex = (backIndex - 1 + size) % size;
length -= 1;
return true;
}
bool push(int value) {
if (size == length) { return false; }
this->queue[backIndex] = value;
backIndex = (backIndex + 1) % size;
length += 1;
return true;
}
int size;
int length = 0;
};
int main() {
int n, k;
cin >> n >> k;
int* window = new int[n + 2];
Queue queue(k);
for (int x = 1; x <= n; x++) { cin >> window[x]; }
for (int x = 1; x <= n; x++) {
while (!queue.empty() && window[queue.back()] > window[x]) { queue.pop_back(); }
queue.push(x);
if (x >= k) {
while (!queue.empty() && (x - queue.front()) >= k) { queue.pop_front(); }
cout << window[queue.front()] << " ";
}
}
while (!queue.empty()) { queue.pop_back(); }
cout << endl;
for (int x = 1; x <= n; x++) {
while (!queue.empty() && window[queue.back()] < window[x]) { queue.pop_back(); }
queue.push(x);
if (x >= k) {
while (!queue.empty() && (x - queue.front()) >= k) { queue.pop_front(); }
cout << window[queue.front()] << " ";
}
}
delete[] window;
cout << endl;
return 0;
}
如果有大佬能看出问题的话非常感谢,或者能提供测试点#3 的数据也可以