点击获取AI摘要

3423. 循环数组中相邻元素的最大差值 E

给你一个 循环 数组 nums ，请你找出相邻元素之间的 最大 绝对差值。

**注意：**一个循环数组中，第一个元素和最后一个元素是相邻的。

示例 1：

输入： nums = [1,2,4]

**输出： ** 3

解释：

由于 nums 是循环的，nums[0] 和 nums[2] 是相邻的，它们之间的绝对差值是最大值 |4 - 1| = 3 。

示例 2：

输入： nums = [-5,-10,-5]

输出： 5

解释：

相邻元素 nums[0] 和 nums[1] 之间的绝对差值为最大值 |-5 - (-10)| = 5 。

提示：

  • 2 <= nums.length <= 100
  • -100 <= nums[i] <= 100

问题分析

给定一个长度为 (n) 的循环数组 nums，要求找出所有相邻元素之间的最大绝对差值。
由于是环形数组，最后一个元素和第一个元素也视为一对相邻元素。

  • 输入：数组 nums，长度满足 (2 \le n \le 100)，元素范围 (-100 \le \text{nums}[i] \le 100)
  • 输出：所有相邻对 ((\text{nums}[i], \text{nums}[i+1]))（含环形末首对）的最大绝对差值

相邻对的绝对差值定义为：

∣a−b∣\lvert a - b \rvert

算法思路

  1. 初始化一个变量 max_diff = 0，用于记录迄今为止的最大绝对差。
  2. 对于普通相邻对，遍历索引 (i) 从 (0) 到 (n-2)：
    • 计算差值 (\lvert \text{nums}[i] - \text{nums}[i+1] \rvert)
    • 若大于 max_diff，则更新 max_diff
  3. 处理环形末首对，计算差值

    wrap_diff=∣nums[n−1]−nums[0]∣\text{wrap\_diff} = \lvert \text{nums}[n-1] - \text{nums}[0] \rvert

    并与 max_diff 比较后更新
  4. 返回最终的 max_diff

时间复杂度

  • 遍历一次长度为 (n) 的数组，做常数时间的绝对值计算和比较，时间复杂度为

    O(n)O(n)

  • 额外只使用若干个标量变量，空间复杂度为

    O(1)O(1)

代码分解

  1. 读取输入并初始化

    • n = len(nums)
    • max_diff = 0

  2. 遍历普通相邻对

    1
    2
    3
    4
    for i in range(n - 1):
        diff = abs(nums[i] - nums[i + 1])
        if diff > max_diff:
            max_diff = diff

  3. 处理环形末首对

    1
    2
    3
    wrap_diff = abs(nums[-1] - nums[0])
    if wrap_diff > max_diff:
        max_diff = wrap_diff

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from typing import List

class Solution:
    def maxAdjacentDistance(self, nums: List[int]) -> int:
        n = len(nums)
        max_diff = 0
        
        # 遍历普通相邻对
        for i in range(n - 1):
            diff = abs(nums[i] - nums[i + 1])
            if diff > max_diff:
                max_diff = diff
        
        # 处理环形末首对
        wrap_diff = abs(nums[-1] - nums[0])
        if wrap_diff > max_diff:
            max_diff = wrap_diff
        
        return max_diff