90分TLE求助
查看原帖
90分TLE求助
11946
兩上星夢楼主2021/1/2 18:57

萌新只有90分,第2个点tle了,能优化吗

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<queue>
using namespace std;

template<class T>void read(T& x)
{
	x = 0; int f = 0; char ch = getchar();
	while (ch < '0' || ch>'9') { f |= (ch == '-'); ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
	x = f ? -x : x;
	return;
}

class Solution {
public:
	vector<int> maxSlidingWindow(vector<int>& nums, int k) {
		int len = nums.size();
		priority_queue<pair<int, int>>a;
		vector<int>ans;
		for (int i = 0; i < k; i++)
			a.push({ nums[i],i });
		ans.push_back(a.top().first);
		for (int i = k; i < len; i++) {
			a.push({ nums[i],i });
			while (a.top().second <= i - k)
				a.pop();
			ans.push_back(a.top().first);
		}
		return ans;
	}
	vector<int> minSlidingWindow(vector<int>& nums, int k) {
		int len = nums.size();
		priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>a;
		vector<int>ans;
		for (int i = 0; i < k; i++)
			a.push({ nums[i],i });
		ans.push_back(a.top().first);
		for (int i = k; i < len; i++) {
			a.push({ nums[i],i });
			while (a.top().second <= i - k)
				a.pop();
			ans.push_back(a.top().first);
		}
		return ans;
	}
	void print(vector<int>a) {
		for (int i = 0; i < a.size(); i++)
			printf("%d ", a[i]);
		printf("\n");
	}
};
Solution t;

void solve() {
	int n, k, num;
	read(n); read(k);
	vector<int> nums;
	for (int i = 1; i <= n; i++) {
		read(num);
		nums.push_back(num);
	}
	t.print(t.minSlidingWindow(nums, k));
	t.print(t.maxSlidingWindow(nums, k));
}

int main() {
	solve();
	return 0;
}
2021/1/2 18:57
加载中...