算法学习记录 8.9 单调栈 单调队列 KMP

单调栈 单调队列 KMP"/>

算法学习记录 8.9 单调栈 单调队列 KMP

1.单调栈

省流：找出数列中每个数左边比它小且离它最近的数

数列中的数是无序的 可以通过将递减数去除的方式将数列缩减成单调数列 便于查找左边最小值

定义数组stk来存储单调递增的数字

单调栈内 如果一个数比它右侧的数小了 那么它的左边的所有数都比他小 

题解

import java.util.Scanner;public class Main{public static void main(String[] args){Scanner sc=new Scanner(System.in);int[] stk=new int[100010];int n=sc.nextInt();int tt=0;//表示栈中的元素for(int i=0;i<n;i++){int x=sc.nextInt();//如果栈非空并且栈顶元素大于x 说明栈顶元素不符合左边比x小的条件 弹出 一直找到栈里比x小 //的第一个数while(tt!=0&&stk[tt]>=x){tt--;}//栈非空就输出栈顶元素 否则说明栈里不存在比它小的元素 输出-1if(tt!=0) System.out.print(stk[tt]+" ");else System.out.print(-1+" ");//新元素进栈stk[++tt]=x;}}
}

时间复杂度：O(n) 

2.单调队列

经典问题：滑动窗口

 定义两个数组a和q 数组a用来存放数列 数组q用来模拟队列 存放的是数列的下标

首先读取数组a的数 判断当前队头存储的下标要在滑动窗口的范围内 如果队头存储的下标超出滑动窗口范围 则窗口向右移动一格

找窗口内的最小值：队列非空 且队列中已有元素与当前数组内循环到的数对比，如果大于等于x，则弹出队列

找窗口内的最大值：队列非空 且队列中已有元素与前数组a内循到的数x对比，如果小于等于x，则弹出队列

x的下标加入队列q

判断窗口大小是否是k 如果是则输出数组a中队列q存储的下标所对应的值

题解

import java.io.*;public class Main{public static void main(String[] args)throws IOException{BufferedReader br=new BufferedReader(new InputStreamReader(System.in));PrintWriter pw=new PrintWriter(new OutputStreamWriter(System.out));int[] q=new int[1000010];int[] a=new int[1000010];int hh=0,tt=-1;String[] s=br.readLine().split(" ");int n=Integer.parseInt(s[0]);int k=Integer.parseInt(s[1]);String[] str=br.readLine().split(" ");for(int i=0;i<n;i++){a[i]=Integer.parseInt(str[i]);}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) pw.print(a[q[hh]]+" ");}pw.println();//循环完毕之后需要对hh，tt进行初始化 再求一遍最大值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) pw.print(a[q[hh]]+" ");}pw.flush();}
}

3.KMP算法

基本概念

文本串：aabaabaaf

模式串：aabaaf

前缀：不包含尾字符 包含头字符的字符串 如：a，aa，aab，aaba，aabaa

后缀：包含尾字符 不包含头字符的字符串 如：f，af，aaf，baaf，abaaf

求模式串的最长相等前后缀（前缀表）

a  aa  aab  aaba  aabaa  aabaaf

0   1     0       1         2          0

步骤：

1.创建next数组

1.1初始化

定义 i 表示后缀末尾， j 表示前缀末尾，s表示模式串

j 初始为0，next[ 0 ]为 0

for(int i=1;i<=s.length();i++)

1.2处理前后缀不相同的情况

j > 0 且遇到冲突即前后缀不相同的情况( s[ i ] != s[ j +1] )，j 进行回退

j 回退到前一位next数组对应的位置 即j=next[j];

1.3处理前后缀相同的情况

前后缀相同的情况( s[ i ] ==s[ j + 1 ] )   j++

1.4更新next数组

next[ i ]= j ;

for(int i=2,j=0;i<=n;i++){//判断j>0且数组s的i和j+1位置上字符是否相同 不相同则j回退 回退到next数组中记录下标去while(j>0&&p[i]!=p[j+1]) j=next[j];//如果相同，j继续移动 记录最长相同前后缀长度if(p[i]==p[j]) j++;//记录每个字符的最大相同前后缀长度next[i]=j;
}

 2.匹配文本串

做法相同 不过是文本串和模式串的匹配对比

for(int i=1,j=0;i<=m;i++){//子串p和字符串s对比 如遇到不相同的字符 j回退while(j>0&&s[i]!=p[j+1]) j=next[j];if(s[i]==p[j+1]) j++;if(j==n){//输出i-n即为子串出现的起始下标//防止后面仍然存在相同子串 j进行一次回退操作j=next[j];}}

 完整代码

import java.io.*;public class Main{public static void main(String[] args)throws IOException{BufferedReader br=new BufferedReader(new InputStreamReader(System.in));BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));int N=100010,M=1000010;int n=Integer.parseInt(br.readLine());String s1=br.readLine();char[] p=new char[N];for(int i=1;i<=n;i++)p[i]=s1.charAt(i-1);int m=Integer.parseInt(br.readLine());String s2=br.readLine();char[] s=new char[M];for(int i=1;i<=m;i++)s[i]=s2.charAt(i-1);int[] next=new int[N];//创建next数组for(int i=2,j=0;i<=n;i++){while(j>0&&p[i]!=p[j+1]) j=next[j];if(p[i]==p[j+1]) j++;next[i]=j;}for(int i=1,j=0;i<=m;i++){while(j>0&&s[i]!=p[j+1]) j=next[j];if(s[i]==p[j+1]) j++;if(j==n){bw.write((i-n)+" ");j=next[j];}}bw.flush();bw.close();br.close();}
}

时间复杂度：O(n+m) 

java常见的快读快写模版：

使用时主函数记得抛出IO异常（throws IOException）

1.快读每一个数字

StreamTokenizer re=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
//读入数据
re.nextToken();
int x=(int)re.nval;

StreamTokenizer 类中 有个方法是 nval 这个方法就是我们读取数据的方法，默认是double类型的，所以我们在读入的时候要将他强制转换类型。
nextToken（）方法，这个方法是我们每次读入数据之前必须要写的，也就是我们读入一个数据之前就要写一个这个方法才行。

2.快读每一行 

BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
PrintWriter pw=new PrintWriter(new OutputStreamWriter(System.out));
//BufferedWriter bw=new BufferedWriter(new OutputStreamReader(System.out));
//读入数据
String s=bf.readLine().split(" ");
int x=Integer.parseInt(s[0]);
//输出数据
pw.print(x);
//bw.write(x);
//刷新流
pw.flush();
//bw.flush();
//bw.close();

快输出PrintWriter输出时 记得最后加个flush()。
也可以是用BufferedReader readLine后，再split。建议使用这个。少写语句，且读一行更快。
参考：