牛客网真题-73-手串

用stack存储每一种颜色的出现的珠子编号。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //n m c
        int[] s = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        HashMap<Integer, Stack<Integer>> map = new HashMap<>();
        for(int i = 1; i <= s[2]; i++){
            map.put(i, new Stack<>());
        }
        //        System.out.println(map.keySet().toString());
        for(int i = 0; i < s[0]; i++){//遍历每一个珠子
            int[] temp = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            for(int j = 1; j < temp.length; j++){
                map.get(temp[j]).add(i + 1);
            }
        }
        int cnt = 0;
        for(int i = 0; i < s[2]; i++){
            int flag = 0;
            Stack stack = map.get(i + 1);
            int size = stack.size();
            int pre = Integer.MAX_VALUE;
            if(!stack.isEmpty()){
                pre = (int) stack.pop();
            }
            int lastest = pre;//lastest最后一个
            while (!stack.isEmpty()) {
                if(pre - (int) stack.peek() < s[1]){
                    flag = 1;
                    break;
                }
                pre = (int) stack.pop();
            }
            //此时pre指向第一个
            if(size > 2 && pre + s[0] - lastest > 0 && pre + s[0] - lastest < s[1]){
                flag = 1;
            }
            cnt+=flag;
        }
        System.out.println(cnt);
    }
}