生活随笔
收集整理的這篇文章主要介紹了
滑动窗口--单调队列
小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
給定一個(gè)大小為 n≤106 的數(shù)組。
有一個(gè)大小為 k 的滑動(dòng)窗口，它從數(shù)組的最左邊移動(dòng)到最右邊。
你只能在窗口中看到 k 個(gè)數(shù)字。
每次滑動(dòng)窗口向右移動(dòng)一個(gè)位置。
以下是一個(gè)例子：
該數(shù)組為 [1 3 -1 -3 5 3 6 7]，k 為 3。
窗口位置 最小值 最大值
[1 3 -1] -3 5 3 6 7 -1 3
1 [3 -1 -3] 5 3 6 7 -3 3
1 3 [-1 -3 5] 3 6 7 -3 5
1 3 -1 [-3 5 3] 6 7 -3 5
1 3 -1 -3 [5 3 6] 7 3 6
1 3 -1 -3 5 [3 6 7] 3 7
你的任務(wù)是確定滑動(dòng)窗口位于每個(gè)位置時(shí)，窗口中的最大值和最小值。
輸入格式
輸入包含兩行。
第一行包含兩個(gè)整數(shù) n 和 k，分別代表數(shù)組長(zhǎng)度和滑動(dòng)窗口的長(zhǎng)度。
第二行有 n 個(gè)整數(shù)，代表數(shù)組的具體數(shù)值。
同行數(shù)據(jù)之間用空格隔開(kāi)。
輸出格式
輸出包含兩個(gè)。
第一行輸出，從左至右，每個(gè)位置滑動(dòng)窗口中的最小值。
第二行輸出，從左至右，每個(gè)位置滑動(dòng)窗口中的最大值。
輸入樣例：
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
.BufferedReader
;
import java
.io
.InputStreamReader
;
public class 滑動(dòng)窗口
{public static void main(String
[] args
) throws Exception
{BufferedReader reader
= new BufferedReader(new InputStreamReader(System
.in
));String
[] s
= reader
.readLine().split(" ");int n
= Integer
.valueOf(s
[0]);int k
= Integer
.valueOf(s
[1]);String
[] chs
= reader
.readLine().split(" ");int nums
[] = new int[n
];for (int i
= 0; i
< n
; i
++) {nums
[i
] = Integer
.valueOf(chs
[i
]);}int queue
[] = new int[n
];int hh
= 0 ,tt
= -1 ; for (int i
= 0; i
< n
; i
++) {if(hh
<= tt
&& i
-k
+1 > queue
[hh
]) hh
++;while(hh
<= tt
&& nums
[i
] <= nums
[queue
[tt
]] ) tt
--;queue
[++tt
] = i
;if(i
>= k
-1) System
.out
.print(nums
[queue
[hh
]]+" ");}System
.out
.println();hh
= 0;tt
= -1;for (int i
= 0; i
< n
; i
++) {if(hh
<= tt
&& i
-k
+1 > queue
[hh
]) hh
++;while(hh
<= tt
&& nums
[i
] >= nums
[queue
[tt
]] ) tt
--;queue
[++tt
] = i
;if(i
>= k
-1) System
.out
.print(nums
[queue
[hh
]]+" ");}System
.out
.println();}
}
總結(jié)
以上是生活随笔為你收集整理的滑动窗口--单调队列的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
