题解 | 左右最值最大差
左右最值最大差
https://www.nowcoder.com/practice/f5805cc389394cf69d89b29c0430ff27
解题思路
这是一个数组划分问题，需要找到一个位置K，使得左右两部分的最大值之差的绝对值最大。
算法步骤：
-
找到数组的最大值：
- 记录最大值和它的位置。
-
遍历所有可能的划分点：
- 对于每个划分点
（从
到
）：
- 计算左部分
的最大值
- 计算右部分
的最大值
- 计算两部分最大值的差的绝对值
- 对于每个划分点
-
更新最大差值：
- 记录所有划分方案中的最大差值。
代码
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
算法及复杂度
- 算法：遍历 + 最大值计算
- 时间复杂度：
，需要遍历所有划分点，每次都要计算左右部分的最大值
- 空间复杂度：
，只使用常数额外空间
基恩士成长空间 386人发布
查看17道真题和解析