兩上星夢 @ 2021-01-02 18:57:59
萌新只有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;
}
by bobbyyang @ 2021-01-08 21:06:39
优先队列第二个点卡常数
除非你手打优先队列加优化或者用O2
可以去用单调队列
by _MJawa_ @ 2021-01-24 17:11:40
开O2还真A了
by _MJawa_ @ 2021-01-24 17:13:15
另:priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>a;
您是怎么拿90的