如何降低「寻找最大值中的最小值」问题的时间复杂度？

给定一个整数数组和另一个整数m，需选择0到m之间的整数替换数组中的所有0，计算替换后数组相邻元素的绝对差，找出每种替换情况的最大绝对差，最终求这些最大值中的最小值。

示例1 #

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

预期输出：

2

解释 #

• 选择i=0替换0后数组为[4,0,3,2]，相邻元素绝对差为[4,3,2]，最大值为4；
• 选择i=1替换0后数组为[4,1,3,2]，相邻元素绝对差为[3,2,1]，最大值为3；
• 选择i=2替换0后数组为[4,2,3,2]，相邻元素绝对差为[2,1,1]，最大值为2；
• 最终取最大值的最小值min(4,3,2)=2。

约束条件 #

• 数组长度为1到10^5；
• 数组元素取值范围为0到10^9；
• m取值范围为0到10^9。

当前代码 #

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)，当m和n均为上限值时（比如m=1e9、n=1e5），会直接超时，必须优化时间复杂度。

我们要找的「所有替换情况的最大绝对差的最小值」具备单调性：如果某个值D是可行的（即存在替换值x∈[0,m]，使得替换后所有相邻元素的绝对差都≤D），那么所有大于D的值也必然可行；反之，如果D不可行，更小的值也一定不可行。基于这个特性，我们可以用二分查找快速定位最小的可行D。

具体步骤 #

1. 确定二分范围

   • 左边界left初始为0；
   • 右边界right初始为数组中可能的最大绝对差（比如取数组非0元素的最大值与m的较大值，因为最大差值不会超过这个范围）。

2. 二分查找核心逻辑
   对中间值mid，判断是否存在x∈[0,m]，使得替换所有0为x后，数组所有相邻元素的绝对差都≤mid：

   • 遍历数组时维护替换后元素的可行取值范围：
     • 初始阶段：若第一个元素是0，初始范围为[0, m]；否则为[list[0], list[0]]。
     • 遍历后续元素：
       • 若当前元素为非0的num：前一个元素的取值范围需满足|num - y| ≤ mid，即y∈[num-mid, num+mid]。将前一个元素的范围与该区间取交集，若交集为空则mid不可行。
       • 若当前元素为0：前一个元素的取值范围可扩展为[prev_low-mid, prev_high+mid]，再将这个范围限制在[0,m]内，若扩展后的范围为空则mid不可行。
     • 遍历结束后，若最终范围非空，说明mid可行，尝试缩小右边界；否则增大左边界。

3. 最终结果
   二分查找结束时，左边界left就是我们要找的最小的最大绝对差。

时间复杂度分析 #

二分查找的次数约为30次（因为max_D最大为1e9，log2(1e9)≈30），每次可行性判断需要遍历数组一次（O(n)），总时间复杂度为O(n log(max_D))，完全适配n=1e5的约束。

示例验证 #

以示例1为例：

• 初始left=0，right=4（原数组最大差值为4）；
• mid=2时，判断可行性：
  • 第一个元素4，范围为[4,4]；
  • 第二个元素0，扩展范围为[4-2,4+2] = [2,6]，结合m=2调整为[2,2]；
  • 第三个元素3，前一个元素范围[2,2]满足|3-y|≤2，交集非空；
  • 第四个元素2，前一个元素范围[2,2]满足|2-y|≤2，交集非空。mid=2可行，调整right=2；
• mid=1时，判断可行性：
  • 第一个元素4，范围[4,4]；
  • 第二个元素0，扩展范围为[3,5]，结合m=2后范围为空，mid=1不可行，调整left=2；
• 最终left=right=2，即为答案。

优化后代码示例 #

static int solve(List<Integer> list, int m) {
    if (list.size() == 1) {
        return 0; // 单个元素无相邻差
    }
    int left = 0;
    int right = 0;
    // 初始化右边界为可能的最大差值
    for (int num : list) {
        if (num != 0) {
            right = Math.max(right, num);
        }
    }
    right = Math.max(right, m);

    while (left < right) {
        int mid = left + (right - left) / 2;
        if (isFeasible(list, m, mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

private static boolean isFeasible(List<Integer> list, int m, int D) {
    int prevLow, prevHigh;
    int first = list.get(0);
    if (first == 0) {
        prevLow = 0;
        prevHigh = m;
    } else {
        prevLow = first;
        prevHigh = first;
    }

    for (int i = 1; i < list.size(); i++) {
        int curr = list.get(i);
        if (curr != 0) {
            // 当前元素固定，前一个元素需满足 |curr - y| <= D
            int currLow = curr - D;
            int currHigh = curr + D;
            prevLow = Math.max(prevLow, currLow);
            prevHigh = Math.min(prevHigh, currHigh);
        } else {
            // 当前元素是0，替换后x的范围需与前一个元素差不超过D
            int currLow = prevLow - D;
            int currHigh = prevHigh + D;
            prevLow = Math.max(currLow, 0);
            prevHigh = Math.min(currHigh, m);
        }
        if (prevLow > prevHigh) {
            return false;
        }
    }
    return true;
}

内容的提问来源于stack exchange，提问作者Learner