Java实现数组局部最大值删除方法无法通过测试用例问题排查

局部最大值指大于自身任意相邻元素的元素，需求为移除原数组中的所有局部最大值元素。

• 示例输入数组：[18, 1, 3, 6, 7, -5]
• 对应预期输出数组：[1, 3, 6, -5]

原有问题实现 #

public static int[] removeLocalMaxima(int[] array){
        int[] result = new int[array.length];
        int j = 0;
 
        for (int i = 0; i < array.length - 1; i++, j++) {
            if(array[i] > array[i + 1]){
                result[j] = array[++i];
            }else {
                result[j] = array[i];
            }
        }
        return  Arrays.copyOf(result, j);
    }

失败测试用例 #

array = new int[1000];
Arrays.fill(array, 15);
array[0] = -20;
array[999] = 25;
array[168] = 18;
array[421] = 0;
actual = LocalMaximaRemove.removeLocalMaxima(array);

assertEquals(998, actual.length);
assertEquals(-20, actual[0]);
assertEquals(15, actual[997]);
assertEquals(0, actual[420]);

该测试用例预期返回数组长度为998、首元素为-20、索引997位置元素为15、索引420位置元素为0，原有实现无法通过断言校验。

逻辑缺陷点 #

1. 局部最大值判定规则完全错误
   原代码仅通过array[i] > array[i+1]作为删除当前元素的依据，完全不符合局部最大值的定义：

• 数组首元素仅需大于右侧相邻元素，即为局部最大值
• 数组尾元素仅需大于左侧相邻元素，即为局部最大值
• 中间位置元素需要同时大于左侧、右侧相邻元素，才属于局部最大值
  原逻辑完全没有校验元素和左侧邻居的大小关系，会大量误删、漏删元素。

2. 尾元素未纳入处理范围
   循环终止条件为i < array.length - 1，遍历全程不会处理最后一个元素。测试用例中尾元素25大于左邻15，属于需要移除的局部最大值，原逻辑既不会对其做判定，也无法正确处理该位置的存储逻辑。

3. 索引跳跃逻辑引发元素错位
   原逻辑判定当前元素比右邻大时，会执行++i直接跳过下一个元素的判定，同时导致后续存入结果数组的元素整体偏移，最终出现元素位置和预期不匹配、长度不符合要求的问题。

修正后实现 #

public static int[] removeLocalMaxima(int[] array){
    if (array == null || array.length == 0) {
        return new int[0];
    }
    int[] result = new int[array.length];
    int j = 0;
    for (int i = 0; i < array.length; i++) {
        boolean isLocalMax = false;
        // 按位置判定当前元素是否为局部最大值
        if (i == 0) {
            // 首元素仅判断右邻
            if (array.length > 1 && array[i] > array[i+1]) {
                isLocalMax = true;
            }
        } else if (i == array.length - 1) {
            // 尾元素仅判断左邻
            if (array[i] > array[i-1]) {
                isLocalMax = true;
            }
        } else {
            // 中间元素同时判断左右邻
            if (array[i] > array[i-1] && array[i] > array[i+1]) {
                isLocalMax = true;
            }
        }
        // 非局部最大值存入结果数组
        if (!isLocalMax) {
            result[j++] = array[i];
        }
    }
    return Arrays.copyOf(result, j);
}

修正后的逻辑严格按照局部最大值定义逐元素判定，不会出现索引错位问题，可以通过给定测试用例的全部断言。

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