郑州做网站多少钱,编程网站网址,新郑做网站推广,自动生成海报的网站theme: channing-cyan
题目
给定一个大小为 n≤10^6 的数组。
有一个大小为 k 的滑动窗口#xff0c;它从数组的最左边移动到最右边。
你只能在窗口中看到 k 个数字。
每次滑动窗口向右移动一个位置。
以下是一个例子#xff1a;
该数组为 [1 3 -1 -3 5 3 6 7]#x…
theme: channing-cyan
题目
给定一个大小为 n≤10^6 的数组。
有一个大小为 k 的滑动窗口它从数组的最左边移动到最右边。
你只能在窗口中看到 k 个数字。
每次滑动窗口向右移动一个位置。
以下是一个例子
该数组为 [1 3 -1 -3 5 3 6 7]k 为 33。
窗口位置最小值最大值[1 3 -1] -3 5 3 6 7-131 [3 -1 -3] 5 3 6 7-331 3 [-1 -3 5] 3 6 7-351 3 -1 [-3 5 3] 6 7-351 3 -1 -3 [5 3 6] 7361 3 -1 -3 5 [3 6 7]37
你的任务是确定滑动窗口位于每个位置时窗口中的最大值和最小值。
输入格式
输入包含两行。
第一行包含两个整数 n 和 k分别代表数组长度和滑动窗口的长度。
第二行有 n 个整数代表数组的具体数值。
同行数据之间用空格隔开。
输出格式
输出包含两个。
第一行输出从左至右每个位置滑动窗口中的最小值。
第二行输出从左至右每个位置滑动窗口中的最大值。
输入样例
8 3
1 3 -1 -3 5 3 6 7输出样例
-1 -3 -3 -3 3 3
3 3 5 5 6 7代码与思路
import java.io.*;public class Main {static BufferedReader reader new BufferedReader(new InputStreamReader(System.in)); // 用于读取输入数据的缓冲读取器static BufferedWriter log new BufferedWriter(new OutputStreamWriter(System.out)); // 用于输出结果的缓冲写入器public static void main(String[] args) throws IOException {// 对输入数据进行初始化String[] s1 reader.readLine().split( );int n Integer.parseInt(s1[0]); // 数组长度int k Integer.parseInt(s1[1]); // 滑动窗口大小String[] s reader.readLine().split( );int[] a new int[n]; // 输入数组for (int i 0; i n; i) {a[i] Integer.parseInt(s[i]); // 初始化输入数组}int[] ans new int[n]; // 存储滑动窗口中的最小或最大值的下标int tt -1, hh 0; // 初始化队列的头尾指针// 查找滑动窗口中的最小值for (int i 0; i n; i) {if (hh tt i - k 1 ans[hh]) {hh;}while (hh tt a[i] a[ans[tt]]) {tt--;}ans[tt] i;if (i 1 k) {log.write(a[ans[hh]] ); // 输出滑动窗口中的最小值}}log.write(\n); // 换行tt -1; // 重新初始化队列的尾指针hh 0; // 重新初始化队列的头指针// 查找滑动窗口中的最大值for (int i 0; i n; i) {if (hh tt i - k 1 ans[hh]) {hh;}while (hh tt a[i] a[ans[tt]]) {tt--;}ans[tt] i;if (i 1 k) {log.write(a[ans[hh]] ); // 输出滑动窗口中的最大值}}// 关闭输入输出流log.flush();reader.close();log.close();}
}
