题解 | #最大差值#
最大差值
https://www.nowcoder.com/practice/a01abbdc52ba4d5f8777fb5dae91b204
解题思路
这是一道求数组中满足条件的最大差值的问题，主要思路如下：
-
问题分析：
- 给定长度为
的数组
- 需要找到满足
的
的最大值
- 即找到后面的数减去前面的数的最大差值
- 给定长度为
-
解决方案：
- 维护一个数组
d记录前个数的最小值
- 遍历数组，用当前值减去前面的最小值，更新最大差值
- 维护一个数组
-
优化点：
- 一次遍历计算前缀最小值
- 一次遍历计算最大差值
- 无需额外空间，可以原地修改
代码
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
int getDis(vector<int>& A, int n) {
if (n < 2) return 0;
// 记录前i个数的最小值
int minVal = A[0];
// 记录最大差值
int maxDiff = 0;
// 遍历数组，更新最大差值
for (int i = 1; i < n; i++) {
maxDiff = max(maxDiff, A[i] - minVal);
minVal = min(minVal, A[i]);
}
return maxDiff;
}
};
import java.util.*;
public class Solution {
public static int getDis(int[] A, int n) {
if (n < 2) return 0;
// 记录前i个数的最小值
int minVal = A[0];
// 记录最大差值
int maxDiff = 0;
// 遍历数组，更新最大差值
for (int i = 1; i < n; i++) {
maxDiff = Math.max(maxDiff, A[i] - minVal);
minVal = Math.min(minVal, A[i]);
}
return maxDiff;
}
}
class Solution:
def getDis(self , A: List[int], n: int) -> int:
if n < 2:
return 0
# 记录前i个数的最小值
min_val = A[0]
# 记录最大差值
max_diff = 0
# 遍历数组，更新最大差值
for i in range(1, n):
max_diff = max(max_diff, A[i] - min_val)
min_val = min(min_val, A[i])
return max_diff
算法及复杂度
- 算法：一次遍历
- 时间复杂度：
- 只需要遍历一次数组
- 空间复杂度：
- 只需要常数额外空间
