leetcode
leetcode 1751 ~ 1800
增量元素之间的最大差值

增量元素之间的最大差值

难度:

标签:

题目描述

代码结果

运行时间: 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,而不是其他数值,例如负无穷大?
在算法中初始化 `ans` 为0而不是负无穷大,是因为题目要求的是最大差值,且差值非负(即 `num[j] - num[i]`,其中 `j > i`)。如果初始化为负无穷大,那么任何正的差值都会更新这个变量,但如果数组中没有任何两个元素满足 `j > i`,即数组完全没有增量元素,按照题目要求应返回 -1。将 `ans` 初始化为0可以直接使用 `ans` 的值来判断是否存在有效的差值,如果遍历结束后 `ans` 仍为0,则说明数组中没有任何元素比先前的元素大,直接返回-1即可。
🦆
在这个算法中,如果数组 `nums` 是单调递减的,`ans` 是否会被正确更新?
如果数组 `nums` 是单调递减的,每个元素比前一个小或相等,那么 `num - cnt` 的结果始终不会大于0(因为 `cnt` 是迄今为止遇到的最小值,也是递减的)。因此,`ans` 不会被更新,它会保持初值0。根据算法逻辑,如果 `ans` 保持为0,算法将返回-1,表示不存在任何两个元素满足 `num[j] > num[i]` 的条件。这是符合题目要求的正确行为。
🦆
算法中提到如果最后 `ans` 的值仍为0,则返回-1。这种情况下怎么判断是因为不存在有效的 `i` 和 `j`,还是因为数组中所有元素相等?
在这个算法中,不需要区分这两种情况。无论是因为数组中所有元素相等,还是因为数组是单调递减的,都没有两个不同的索引 `i` 和 `j` 使得 `num[j] > num[i]`。在这两种情况下,`ans` 都会保持初始化的值0,最终算法返回-1。因此,这种设计恰当地处理了数组中元素完全相同或单调递减的情况,返回-1表示没有找到有效的索引对。
🦆
在更新 `cnt` 为 `min(cnt, num)` 时,是否考虑了当前 `num` 可能正是 `cnt` 之后的最大值所需的最小值,会不会影响后续差值的计算?
这个更新步骤是合理的。在每次迭代中,通过将 `cnt` 更新为 `cnt` 和当前元素 `num` 的最小值,确保 `cnt` 总是记录到当前位置为止的最小元素。这样,对于任何后续的元素,计算其与 `cnt` 的差值总是基于到目前为止最小的值进行的,这是计算最大差值所需的条件。因此,不会影响后续差值的计算,反而是确保了差值计算的正确性。

相关问题