数组数据结构问题：按照给定规则计算数组的总最佳值

现有代码的问题 #

• 循环边界错误：你设置的循环终止条件为i<A.length-2，会漏掉最后一个待校验的倒数第二个元素（即索引为A.length-2的元素），正确遍历范围应为索引1到A.length-2（包含两端）
• 规则b的判断逻辑缺失：代码中直接使用未定义的j和h变量，没有遍历左右区间校验是否满足「大于左边所有元素、小于右边所有元素」的条件，无法通过编译
• 规则优先级错误：规则b的分值更高，如果一个元素同时满足规则a和b，应该优先取2分，你当前先判断a再判断b的else if逻辑会导致高优先级的规则b被跳过，计算结果错误

实现思路 #

为了避免每次判断规则b都重复遍历左右区间（时间复杂度优化到O(N)），我们先预处理两个辅助数组：

• leftMax[i]：存储区间[0, i-1]的最大值，判断A[i]是否大于左边所有元素，只需校验A[i] > leftMax[i]
• rightMin[i]：存储区间[i+1, N-1]的最小值，判断A[i]是否小于右边所有元素，只需校验A[i] < rightMin[i]
  之后遍历所有非首尾元素，优先判断规则b，不满足再判断规则a即可

完整可运行代码 #

public class BestValueCalculator {
    public static void main(String[] args) {
        int[] A = {2,1,3,9,20,7,8};
        int n = A.length;
        if (n <= 2) { // 没有需要计算的元素直接返回0
            System.out.println(0);
            return;
        }
        // 预处理leftMax数组
        int[] leftMax = new int[n];
        leftMax[1] = A[0];
        for (int i = 2; i < n; i++) {
            leftMax[i] = Math.max(leftMax[i-1], A[i-1]);
        }
        // 预处理rightMin数组
        int[] rightMin = new int[n];
        rightMin[n-2] = A[n-1];
        for (int i = n-3; i >= 0 ; i--) {
            rightMin[i] = Math.min(rightMin[i+1], A[i+1]);
        }
        int result = 0;
        // 遍历所有非首尾元素
        for (int i = 1; i <= n-2; i++) {
            // 优先判断规则b
            if (A[i] > leftMax[i] && A[i] < rightMin[i]) {
                result += 2;
            } else if (A[i-1] < A[i] && A[i] < A[i+1]) { // 再判断规则a
                result += 1;
            }
        }
        System.out.println(result);
    }
}

示例运行说明 #

针对输入数组[2,1,3,9,20,7,8]：

• 元素3（索引2）大于左边所有元素，小于右边所有元素，加2
• 元素9（索引3）满足相邻递增，加1
• 其余元素均不满足规则，总和为3，和示例输出一致

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