数据结构与算法面试题：给定 n 个非负整数 a1,a2,a3,...,an，每个数代表坐标中的一个点(i, ai)，请找出两个点之间的最大距离。（提示：动态规划）

GeekLiHua

发布于 2025-01-21 13:39:00

4480

文章被收录于专栏：JavaJava

数据结构与算法面试题：给定 n 个非负整数 a1,a2,a3,…,an，每个数代表坐标中的一个点(i, ai)，请找出两个点之间的最大距离。（提示：动态规划）

简介：给定 n 个非负整数 a1,a2,a3,…,an，每个数代表坐标中的一个点(i, ai)，请找出两个点之间的最大距离。（提示：动态规划）

算法思路

算法实现思路：

使用动态规划的方法进行求解。具体来说，用left[i]表示第i个数左侧最小的数，用right[i]表示第i个数右侧最大的数。初始化left[0] = a[0]和right[n - 1] = a[n - 1]。
遍历数组，求解left和right数组。对于left数组，我们从前往后遍历a数组，更新left[i+1] = min(left[i], a[i+1])；对于right数组，我们从后往前遍历a数组，更新right[i-1] = max(right[i], a[i-1])。
最后遍历数组，计算最大差值maxDiff = max(maxDiff, right[i] - left[i])，其中0 <= i < n。

使用C++代码实现，注释详细：

class Solution {
public:
    int maxDistance(vector<int>& nums) {
        int n = nums.size();
        vector<int> left(n, 0), right(n, 0); // 定义两个数组分别存储对于每个元素i来说的左边最小和右边最大的数
        left[0] = nums[0]; // 初始化，左边最小为nums[0]
        right[n - 1] = nums[n - 1]; // 初始化，右边最大为nums[n-1]

        for (int i = 1; i < n; i++) { // 更新left数组
            left[i] = min(left[i - 1], nums[i]);
        }

        for (int i = n - 2; i >= 0; i--) { // 更新right数组
            right[i] = max(right[i + 1], nums[i]);
        }

        int maxDiff = 0;
        for (int i = 0; i < n; i++) { // 遍历数组，计算左边最小和右边最大之差的最大值
            maxDiff = max(maxDiff, right[i] - left[i]);
        }
        return maxDiff;
    }
};

由于动态规划思路本身简单明了，代码实现也比较简单。关键在于对left和right数组更新方法的理解，这样才能理解所编写代码的含义。

java版本

class Solution {
    public int maxDistance(int[] nums) {
        int n = nums.length;
        int[] left = new int[n];
        int[] right = new int[n];
        left[0] = nums[0];
        right[n - 1] = nums[n - 1];

        for (int i = 1; i < n; i++) {
            left[i] = Math.min(left[i - 1], nums[i]);
        }

        for (int i = n - 2; i >= 0; i--) {
            right[i] = Math.max(right[i + 1], nums[i]);
        }

        int maxDiff = 0;
        for (int i = 0; i < n; i++) {
            maxDiff = Math.max(maxDiff, right[i] - left[i]);
        }
        return maxDiff;
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-01-20，如有侵权请联系 cloudcommunity@tencent.com 删除

数据结构与算法