怎么通过所有的网站推广广告,网站new图标,小程序网站怎么做,wordpress搜索结果优先标签数组模拟单调队列
分析
以k3举例#xff1a;
(1)利用单调队列的性质#xff1a; 1最小值#xff1a;确保队列单调递增#xff0c;处理后#xff0c;队头即是最小值。 2最大值#xff1a;确保队列单调递减#xff0c;处理后#xff0c;队头即是最大值…数组模拟单调队列
分析
以k3举例
(1)利用单调队列的性质 1最小值确保队列单调递增处理后队头即是最小值。 2最大值确保队列单调递减处理后队头即是最大值。 那么怎么确保单调性
关键代码 以最小值为例 while(hhtta[q[tt]]a[i])tt--;
(2)这里的a[q[tt]]a[i]即是确保单调性的关键 求最大值这里修改成a[q[tt]]a[i]确保单调递减即可其余均一致。) 解读每次添加元素到队尾后将该队尾元素和队头元素进行比较如果这个元素大于(等于)队头元素就说明队尾元素并不是需要的最小值队头元素比它更适合更有潜力成为最小值所以将该队尾元素抹掉则t- -。再继续添加继续判断。 换句话来说不满足单调递增的性质需要将不满足的元素给剔掉确保单调性。
确保单调性后为什么输出队头即可? 确保单调性后我们得到的队尾元素即是最小/大值此时如果只有一个元素即队头输出队头即可。 如果还有剩余元素需要将队列中剩余的其他元素剔掉让队列中只有一个元素此时队头指向队尾输出队头即可。 综上输出队头即可。
那又怎么剔掉单调处理后队列中还有多余的元素(出队多余元素 关键代码 以最小值为例 if(hhtti-k1q[hh])hh;
(3)这里的i-k1即是确保出队的关键 推断如下
这里的出队有两层意义
1用于更新原队列的hh一个个出掉范围更新下去。 2用于队头元素的出队如果tt- -后,队列中只有1个元素即队头输出即可。 如果队列中还剩1、2个元素,则需要出队不断出掉队尾元素前的元素即hh
(4)最后由单调性的确保和队头元素的确保只需要输出队头元素即可。
队列过程变化图
图1 图2 代码
import java.util.*;
import java.io.*;
public class Main{static int N100010;static int n,k;static int hh,tt;static int q[]new int [N];static int a[]new int [N];public static void main(String []args) throws IOException{BufferedReader in new BufferedReader(new InputStreamReader(System.in));PrintWriter out new PrintWriter(new OutputStreamWriter(System.out));String []st in.readLine().split( );nInteger.parseInt(st[0]);kInteger.parseInt(st[1]);String []str in.readLine().split( );for(int i0;in;i){a[i]Integer.parseInt(str[i]);}hh 0;tt-1;//求最小值for(int i0;in;i){//出队if(hhtti-k1q[hh])hh;//出队//t--更新到最后如果还剩1-2个元素则把他们都剔掉。//此时队头指向队尾再输出队头即可。while(hhtta[q[tt]]a[i])tt--;//保证队列单调递增那么队尾即是最小值。//具体为添加进队尾的元素如果比队头的元素要大就tt--即把该元素给剔掉。q[tt]i;//添加元素下标到队列尾if(ik-1)//在k的范围队列中输出元素out.print(a[q[hh]] );}out.println();//求最大值hh0;tt-1;for(int i0;in;i){//出队if(hhtti-k1q[hh])hh;//t--更新到最后如果还剩1-2个元素则把他们都剔掉。//此时队头指向队尾再输出队头即可。while(hhtta[q[tt]]a[i])tt--;//保证队列单调递减那么队尾即是最大值。//具体为添加进队尾的元素如果比队头的元素要小就tt--即把该元素给剔掉。q[tt]i;//添加元素下标到队列尾if(ik-1)//在k的范围队列中输出元素out.print(a[q[hh]] );}out.flush();
}
}
