题解 | #数组中两个字符串的最小距离#

思路：贪心

1.如果暴力：两层for循环枚举，数据范围是10^5,会超时

2.用贪心（dp）来优化

3.用若干个变量来标记某个位置前驱的最优解（常用优化方法）预处理思想

只管左边，不管右边。当遍历到后面的时候，向左看，会包含之前右边的情况。

4.prev1:标记的是遍历到i位置时，左边最近符合要求的下标,

5.prev2：标记的是i遍历到了符合要求的另一个下标

时间复杂度：o(n)

代码：

import java.io.*;
public class Main {
    public static void main(String[] args)throws Throwable {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        String[]str = reader.readLine().split(" ");
        String s1 = str[0];
        String s2 = str[1];
        int prev1= -1,prev2 = -1,ret = 0x3f3f3f3f;//无穷大
        for(int i = 0;i<n;i++){
             String s = reader.readLine();
            if(s.equals(s1)){//去前面找最近的s2
                if(prev2 !=-1){//存在s2
                     ret = Math.min(ret,i-prev2);
                }
                prev1 = i;
            }else if(s.equals(s2)){//去找前面最近的s1;
                if(prev1!=-1){
                    ret = Math.min(ret,i-prev1);
                }
                prev2 = i;
            }
        }
        System.out.println(ret == 0x3f3f3f3f?-1:ret);
    }
}