测试点#3 WA了,想知道什么原因
查看原帖
测试点#3 WA了,想知道什么原因
967972
Rindong楼主2023/10/20 14:54

是我的队列实现写错了吗?还是哪里有问题?用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 的数据也可以

2023/10/20 14:54
加载中...