增量元素之间的最大差值
难度:
标签:
题目描述
代码结果
运行时间: 26 ms, 内存: 16.1 MB
// Solution for finding the maximum difference using Java Streams
// Streams are used to find the max and min values efficiently
// Given an array nums, find the maximum difference nums[j] - nums[i] where 0 <= i < j < n and nums[i] < nums[j]
// If no such pair exists, return -1
import java.util.stream.IntStream;
public class Solution {
public int maximumDifference(int[] nums) {
int n = nums.length;
int minValue = nums[0];
int maxDifference = IntStream.range(1, n)
.map(j -> nums[j] > minValue ? nums[j] - (minValue = Math.min(minValue, nums[j])) : -1)
.max()
.orElse(-1);
return maxDifference;
}
}
解释
方法:
该题解采用一次遍历的方法来解决问题。首先,定义一个变量 `cnt`,用于存储目前为止遇到的最小值。然后,遍历整个数组,对每个元素,更新 `cnt` 为当前元素和 `cnt` 中较小的一个,同时计算当前元素与 `cnt` 的差值,并更新最大差值 `ans`。遍历完成后,如果 `ans` 仍为0,说明没有找到满足条件的 `i` 和 `j`,因此返回 -1。否则,返回 `ans`,即最大差值。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在算法中选择将初始化的最大差值 `ans` 设为0,而不是其他数值,例如负无穷大?
▷🦆
在这个算法中,如果数组 `nums` 是单调递减的,`ans` 是否会被正确更新?
▷🦆
算法中提到如果最后 `ans` 的值仍为0,则返回-1。这种情况下怎么判断是因为不存在有效的 `i` 和 `j`,还是因为数组中所有元素相等?
▷🦆
在更新 `cnt` 为 `min(cnt, num)` 时,是否考虑了当前 `num` 可能正是 `cnt` 之后的最大值所需的最小值,会不会影响后续差值的计算?
▷