Java 以较小的时间复杂度找到最大值的最小值

我正在考虑这个代码挑战:

给出一个array的整数和另一个整数m.

Select 一个介于0和m之间的整数，并用该整数替换整数输入数组中出现的0，然后判断相邻数组项之间的绝对差异.

找出每种情况下的最大绝对差值.然后finally找出所有这些最大值中的minimum个.

Example 1:个

array = [4,0,3,2]
m = 2;

Expected output:个

2

Explanation:个

• Select i=0，将数组中出现的所有0替换为值i，在本例中为0:[4，0，3，2].求出相邻元素之间的绝对差[4-0，3-0，3-2]=[4，3，2].这些绝对值中的最大值为4.
• Select i=1，将数组中出现的所有0替换为值i，在本例中为1:[4，1，3，2].求相邻元素之间的绝对差[4-1，3-1，3-2]=[3，2，1].这些绝对值中的最大值为3.
• Select i=2，将数组中出现的所有0替换为值i，在本例中为2:[4，2，3，2].求相邻元素之间的绝对差[4-2，3-2，3-2]=[2，1，1].这些绝对值中的最大值为2.
• 最后，所有极大值的最小值是min(4，3，2)=2，这就是答案.

constraints:个

• array有1到10个⁵项
• array[i]的范围从0到10⁹
• m的范围从0到10⁹

这是我的代码:

static int solve(List<Integer> list, int m) {
    int response = Integer.MAX_VALUE;
    int n = list.size();
    for(int i=0; i<=m ;i++) {
        int j = list.get(0);
        int max = 0;
        if(j==0) j = i;
        for(int k=1; k<n; k++) {
            int e = list.get(k);
            if(e==0) e = i;
            int abs = Math.abs(e-j);
            max = Math.max(max, abs);
            j = e;
        }
        response = Math.min(response, max);
    }
    return response;
}

该编码的时间复杂度为O(m*n).

解决此问题的正确方法是什么，以降低时间复杂性？