NC50528 滑动窗口
#include <iostream> using namespace std; const int maxn = 1000010; int arr[maxn]; int du[maxn]; int main() { int n, k; cin >> n >> k; for (int i = 1; i <= n; i++) { cin >> arr[i]; } int l = 0; int r = 1; du[0] = 1; //if (k == 1)cout << arr[1]<<" "; for (int i = 2; i <= n; i++) { if (i - du[l] >= k&& (l < r))l++; while (l < r && arr[du[r - 1]] >= arr[i])r--; du[r++] = i; if (i >= k)cout << arr[du[l]] << " "; } cout << endl; l = 0; r = 1; du[0] = 1; for (int i = 2; i <= n; i++) { if (i - du[l] >= k && (l < r))l++; while (r > l && arr[du[r - 1]] <= arr[i])r--; du[r++] = i; if (i >= k)cout << arr[du[l]] << " "; } }
题解汇总 文章被收录于专栏
无