解题思路

这是一个数组划分问题，需要找到一个位置K，使得左右两部分的最大值之差的绝对值最大。

算法步骤：

  1. 找到数组的最大值：

    • 记录最大值和它的位置。

  2. 遍历所有可能的划分点：

    • 对于每个划分点 （从 到 ）：
    • 计算左部分 的最大值
    • 计算右部分 的最大值
    • 计算两部分最大值的差的绝对值

  3. 更新最大差值：

    • 记录所有划分方案中的最大差值。

代码

class MaxGap {
public:
    int findMaxGap(vector<int>& A, int n) {
        if (n <= 1) return 0;
        
        int maxGap = 0;
        
        // 遍历所有可能的划分点
        for (int k = 0; k < n - 1; k++) {
            // 计算左部分最大值
            int leftMax = A[0];
            for (int i = 0; i <= k; i++) {
                leftMax = max(leftMax, A[i]);
            }
            
            // 计算右部分最大值
            int rightMax = A[k + 1];
            for (int i = k + 1; i < n; i++) {
                rightMax = max(rightMax, A[i]);
            }
            
            // 更新最大差值
            maxGap = max(maxGap, abs(leftMax - rightMax));
        }
        
        return maxGap;
    }
};

import java.util.*;
public class MaxGap {
    public int findMaxGap(int[] A, int n) {
        if (n <= 1) return 0;
        
        int maxGap = 0;
        
        // 遍历所有可能的划分点
        for (int k = 0; k < n - 1; k++) {
            // 计算左部分最大值
            int leftMax = A[0];
            for (int i = 0; i <= k; i++) {
                leftMax = Math.max(leftMax, A[i]);
            }
            
            // 计算右部分最大值
            int rightMax = A[k + 1];
            for (int i = k + 1; i < n; i++) {
                rightMax = Math.max(rightMax, A[i]);
            }
            
            // 更新最大差值
            maxGap = Math.max(maxGap, Math.abs(leftMax - rightMax));
        }
        
        return maxGap;
    }
}

class MaxGap:
    def findMaxGap(self, A, n):
        if n <= 1:
            return 0
            
        max_gap = 0
        
        for k in range(n - 1):
            # left part max
            left_max = max(A[:k + 1])
            
            # right part max
            right_max = max(A[k + 1:])
            
            # update max gap
            max_gap = max(max_gap, abs(left_max - right_max))
            
        return max_gap

算法及复杂度

  • 算法：遍历 + 最大值计算
  • 时间复杂度：，需要遍历所有划分点，每次都要计算左右部分的最大值
  • 空间复杂度：，只使用常数额外空间