数组中最远有效对查找：求最大K满足K=|i-j|=|A[i]-A[j]|

问题描述 #

给定包含N个整数的数组A，需找到最大的K（取值范围0到N-1），满足存在位置对(i, j)使得K = |i − j| = |A[i] − A[j]|，其中|x|表示x的绝对值，即下标间距等于对应元素值的差的绝对值。i=j时单个位置自身始终是K=0的有效对。

接口要求 #

请实现如下Java类中的方法：

class Solution { 
    public int solution(int[] A); 
}

该函数接收数组A为参数，返回符合条件的最大K值。

示例说明 #

输入：A = [2, 2, 2, 1]
输出：1
解释：最远有效对为A[2] = 2和A[3] = 1，满足1 = |2 − 3| = |2 − 1|。

解题思路 #

要找最大的K，我们可以从最大可能的K值（即数组长度减1）倒序遍历，每遍历一个K就检查是否存在满足条件的下标对：

• 对于固定K，所有符合间距要求的下标对都满足j = i + K，i的取值范围是0到A.length - K - 1
• 只要找到任意一对(i, i+K)满足|A[i+K] - A[i]| == K，当前K就是最大值，直接返回即可
• 最坏情况遍历到K=0时一定满足条件，保证结果合法

完整实现代码 #

class Solution {
    public int solution(int[] A) {
        int n = A.length;
        // 从最大的可能K开始倒序检查
        for (int k = n - 1; k >= 0; k--) {
            // 遍历所有间距为k的下标对
            for (int i = 0; i <= n - k - 1; i++) {
                int j = i + k;
                if (Math.abs(A[j] - A[i]) == k) {
                    return k;
                }
            }
        }
        // 理论上不会走到这里，K=0一定满足
        return 0;
    }
}

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