我们可以在O(n log n)时间和O(n)空间中解决此问题。首先请注意，任何指定的颜色必须与相同颜色的相邻元素相距m个元素，否则我们将使约束无效。

将每个这种颜色相同的元素列表（仅由彼此之间的距离定义）分隔到自己的列表中并进行排序。

现在将所有m排序列表合并到一个排序列表中，其中每个值还与其来源列表颜色的标签配对（例如，合并列表可以是元组）。 / p>

（或者，我们可以先创建整个标签列表，然后对那个进行排序。）

使用大小为m的滑动窗口在排序的，带有标签的列表上进行迭代，从而每次仅允许每种颜色的一个元素留在窗口中。 （我们可以使用哈希图或简单数组来跟踪窗口。请记住，在这种情况下，窗口具有唯一标签，而不是标签列表的连续子数组。）在迭代过程中更新窗口中存在的最小范围以确定答案。

我认为您可以对数字进行排序（但要跟踪其颜色），然后从开始就逐步查看结果，首先要培养出候选人以显示所有颜色（因此head将涵盖子列表中的唯一颜色），然后缩小它，以便从tail抛出重复的颜色（因此它也指向唯一的颜色），然后检查到目前为止是否是最佳候选，然后丢弃{{ 1}}（这样就会丢失颜色），然后再次使用head：

tail

输出（一个3色常量随机序列-因为提供了种子-您的2色示例和您所修复的错误的测试用例）：

import java.util.Arrays;
import java.util.List;
import java.util.Random;

public class NewClass {
    public static void doThing(int nums[],int m){
        int n=nums.length;
        ColorNumber l[]=new ColorNumber[n];
        for(int i=0;i<n;i++)
            l[i]=new ColorNumber(nums[i],i%m);
        System.out.println(Arrays.asList(l));
        Arrays.sort(l,null);
        List printlist=Arrays.asList(l);
        System.out.println(printlist);
        int present[]=new int[m];
        int head=0,tail=0;
        int minhead=0,mintail=0,mindiff=Integer.MAX_VALUE;
        while(head<n){
            System.out.println("try growing");
            int i=0;
            while(i<m && head<n){
                while(present[i]==0 && head<n){
                    present[l[head].color]++;
                    head++;
                }
                //if(present[i]>0)i++;           // the bug
                while(i<m && present[i]>0)i++;   // the fix
            }
            if(i==m){
                System.out.println(printlist.subList(tail,head));
                System.out.println("try shrinking");
                while(present[l[tail].color]>1){
                    present[l[tail].color]--;
                    tail++;
                }
                int diff=l[head-1].number-l[tail].number;
                System.out.println(printlist.subList(tail,head)+" diff: "+diff);
                if(diff<mindiff){minhead=head;mintail=tail;mindiff=diff;}
                present[l[tail].color]--;
                tail++;
            }
        }
        System.out.println("min: "+mindiff+","+printlist.subList(mintail,minhead));
    }

    static class ColorNumber implements Comparable<ColorNumber>{
        final int number;
        final int color;

        public ColorNumber(int number,int color) {
            this.number = number;
            this.color = color;
        }

        @Override
        public int compareTo(ColorNumber o) {
            return number-o.number;
        }

        @Override
        public String toString() {
            return number+"("+color+")";
        }
    }

    public static void main(String args[]){
        Random r=new Random(0);
        int nums[]=new int[10];
        for(int i=0;i<nums.length;i++)
            nums[i]=r.nextInt(100);
        doThing(nums,3);
        System.out.println("---");
        doThing(new int[]{10,20,15,28},2);
        System.out.println("---");
        doThing(new int[] {2,1},2);              // test case for bug
    }
}

在输出中，只有最低值和最高值的颜色才是唯一的，可以随意选择中间的元素，因为它们不会造成差异（此代码将它们全部输出，就像第一个序列（[60(0),48(1),29(2),47(0),15(1),53(2),91(0),61(1),19(2),54(0)] [15(1),54(0),60(0),91(0)] try growing [15(1),47(0)] try shrinking [15(1),47(0)] diff: 32 try growing [19(2),48(1)] try shrinking [29(2),48(1)] diff: 19 try growing [47(0),53(2)] try shrinking [47(0),53(2)] diff: 6 try growing [48(1),54(0)] try shrinking [48(1),54(0)] diff: 6 try growing [53(2),61(1)] try shrinking [53(2),61(1)] diff: 8 try growing min: 6 [47(0),53(2)] --- [10(0),20(1),15(0),28(1)] [10(0),28(1)] try growing [10(0),20(1)] try shrinking [15(0),20(1)] diff: 5 try growing min: 5 [15(0),20(1)] --- [2(0),1(1)] [1(1),2(0)] try growing [1(1),2(0)] try shrinking [1(1),2(0)] diff: 1 min: 1,[1(1),2(0)] ）中的最后一次尝试。如果需要特定的输出，则可以使用一些[53(2),61(1)]或在颜色上进行Set循环，为每种颜色仅打印一个（遇到的第一个）元素（并使用简单的for）。