数据结构与算法面试题：给定 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; } }
