牛客网真题-60-头条校招

最大最小问题一般都先考虑能不能dp，但这道题不需要dp。
三个数从小到大，间隔10，排序+贪心就好了，最小的三个一组，利用一个容量为queue存储数据，当now-pre<=10,就可以进队。
根据queue的size判断产生结果。可以利用pre和size直接模拟queue，也可以理解为马尔科夫状态过程：当前状态只与前一个状态有关。

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] ints = new int[n];
        for(int i = 0; i < ints.length; i++){
            ints[i] = scanner.nextInt();
        }
        Arrays.sort(ints);
        int index = 0;
        int pre = -1, size = 0, cnt = 0;
        while (index < n) {
//            System.out.println("pre " + pre + " size " + size);
            if(size == 0){
                pre = ints[index];
                size = 1;
            }else if(size == 1){
                if(ints[index] - pre <= 10){
                    pre = ints[index];
                    size = 2;
                }else{
                    pre = ints[index];
                    cnt += 2;
                    size = 1;
                }
            }else{
                if(ints[index] - pre <= 10){
                    pre = -1;
                    size = 0;
                }else{
                    pre = ints[index];
                    cnt++;
                    size = 1;
                }

            }
            index++;
        }
        if(size == 2){
            cnt++;
        }else if(size == 1){
            cnt += 2;
        }
        System.out.println(cnt);
    }
}