登陆建设官方网站,鹤壁建设网站推广公司,seo查询什么意思,王建设医生个人网站给定一个大小为 n≤10^6 的数组。 有一个大小为 k 的滑动窗口#xff0c;它从数组的最左边移动到最右边。 你只能在窗口中看到 k 个数字。 每次滑动窗口向右移动一个位置。 以下是一个例子#xff1a; 该数组为 [1 3 -1 -3 5 3 6 7]#xff0c;k 为 33。 窗口位置最小值最大… 给定一个大小为 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 个整数代表数组的具体数值。 同行数据之间用空格隔开。 输出格式: 输出包含两个。 第一行输出从左至右每个位置滑动窗口中的最小值。 第二行输出从左至右每个位置滑动窗口中的最大值。 解题思路 如果朴素的做法将每次得到的窗口进行遍历找最小值。时间复杂度大概是nk不出意外是会超时的。如何对其进行优化呢
首先以数组q[N]作为本题队列a[N]存入输入的元素。我们知道下标和元素具有一 一对应的关系所以q[i]不是存入元素所对应的值而是元素所对应的下标。 在这里设hh 0为头指针tt - 1为尾指。
首先应该明确窗口的特点即内部元素的数量在k的时候即可输出最内部最小值和最大值。此后每移动一下就再次输出一次。这恰好哦可以用循环变量i来表示,如下窗口
[a,b,c,d.....]
0 i 窗口内部元素的数量可用 i - 0 1来表示当窗口内数量够k个的时候即可输出即i - 0 1 k即 i k - 1。
有趣的是当 0~i 2 中c为最小值的时候当窗口向右边移动的时候
[b,c,d,e.....]
1 i 1 min c
[c,d,e,f.....]
2 i 2 min c
不难看出窗口在移动的时候最小值仍是c,如果能用队列存入最小值的下标(即q[tt] 2),那就避免重新遍历窗口的麻烦。那问题来了设立队列只是为了存入一个最小值的吗?这显然不是如下窗口继续向右移动
[d,e,f,g.....]
3 i 3 min ? 由此可见如果队列里值只存入c的下标,当窗口不包含c的时候队列内的 q[tt] 2 也就没用了。
那么需要队列理想的情况是让队列内存入 最小元素下标第二小元素下标第三小元素下标.......
当窗口不再包含最小元素的时候那么就可以在队列内删去了那么第二小元素就理应成为新的最小元素了以此类推队列头部元素一直是符合条件的最小元素下标。
至于如何输出最大值和上述反着来即可。
理论成立代码如下未加速版
import java.util.*;public class Main {public static int N 1000010;public static void main(String[] args) {Scanner sc new Scanner(System.in);int a[] new int [N];//数组int q[] new int [N];//队列int n sc.nextInt();int k sc.nextInt();for(int i 0; i n; i ) a[i] sc.nextInt();int hh 0, tt -1;//队头队尾q[hh]存入最小元素下标for(int i 0; i n; i ) {//找最小值if(hh tt q[hh] i - k 1) hh ;//在滑动窗口的外面移动左窗口while(hh tt a[q[tt]] a[i]) tt--;//队尾不比添加进来的数小那就没用删掉。q[ tt] i;//添加元素。if(i k - 1) {if(i n-1)System.out.println(a[q[hh]]);elseSystem.out.print(a[q[hh]] ); } }
//输出最大值hh 0; tt -1;for(int i 0; i n; i ) {if(hh tt q[hh] i - k 1 ) hh ;while(hh tt a[q[tt]] a[i]) tt --;q[ tt] i;if(i k - 1) {if(i n - 1)System.out.print(a[q[hh]]);elseSystem.out.print(a[q[hh]] );}}}
}
由于最后一个数据过于庞大时间超时了想通过得用如下的加速版
import java.io.*;
import java.util.*;;
public class Main {public static int N 1000010;public static void main(String[] args) throws IOException {// TODO Auto-generated method stubScanner sc new Scanner(new BufferedInputStream(System.in));BufferedWriter sout new BufferedWriter(new OutputStreamWriter(System.out));int a[] new int [N];//数组int q[] new int [N];//队列int n sc.nextInt();int k sc.nextInt();for(int i 0; i n; i ) a[i] sc.nextInt();int hh 0, tt -1;//队头队尾q[hh]存入最小元素下标for(int i 0; i n; i ) {//找最小值if(hh tt q[hh] i - k 1) hh ;//在滑动窗口的外面移动左窗口while(hh tt a[q[tt]] a[i]) tt--;//队尾不比添加进来的数小那就没用删掉。q[ tt] i;//添加元素。if(i k - 1) {sout.write(a[q[hh]] ); } }sout.write(\n);//输出最大值hh 0; tt -1;for(int i 0; i n; i ) {if(hh tt q[hh] i - k 1 ) hh ;while(hh tt a[q[tt]] a[i]) tt --;q[ tt] i;if(i k - 1) {sout.write(a[q[hh]] );}}sout.close();sc.close();}}
