LeetCode 3105. Longest Strictly Increasing or Strictly Decreasing Subarray

Posted on In Views:
LeetCode exercise

3105. Longest Strictly Increasing or Strictly Decreasing Subarray

You are given an array of integers nums. Return the length of the longest subarray of nums which is either strictly increasing or strictly decreasing.

解题思路

  1. 遍历数组：我们需要遍历 nums 数组，找到最长的严格递增或严格递减子数组的长度。
  2. 使用两个计数器：
    • inc_len 记录当前递增子数组的长度。
    • dec_len 记录当前递减子数组的长度。
  3. 更新逻辑：
    • 如果 nums[i] > nums[i - 1]，说明递增，递增计数器 inc_len 增加，并重置递减计数器 dec_len。
    • 如果 nums[i] < nums[i - 1]，说明递减，递减计数器 dec_len 增加，并重置递增计数器 inc_len。
    • 如果相等，则重置两个计数器为 1。
  4. 维护最大值：在每一步更新 max_len，确保获取最长的子数组长度。

代码实现 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def longest_strictly_increasing_or_decreasing_subarray(nums):
    if not nums:
        return 0

    inc_len = dec_len = 1  # 初始化递增和递减子数组的长度
    max_len = 1  # 记录最大子数组长度

    for i in range(1, len(nums)):
        if nums[i] > nums[i - 1]:  # 递增情况
            inc_len += 1
            dec_len = 1  # 重置递减长度
        elif nums[i] < nums[i - 1]:  # 递减情况
            dec_len += 1
            inc_len = 1  # 重置递增长度
        else:  # 相等时，重置两个长度
            inc_len = dec_len = 1

        max_len = max(max_len, inc_len, dec_len)  # 更新最大值

    return max_len

时间复杂度分析

  • 遍历一次数组，时间复杂度为 O(n)，其中 n 是 nums 的长度。

示例

1
2
3
print(longest_strictly_increasing_or_decreasing_subarray([1, 2, 3, 4, 3, 2, 1]))  # 输出: 7
print(longest_strictly_increasing_or_decreasing_subarray([5, 4, 3, 2, 1]))  # 输出: 5
print(longest_strictly_increasing_or_decreasing_subarray([10, 20, 30, 10, 5, 1, 2, 3, 4]))  # 输出: 5

总结

  • 维护两个变量 inc_len 和 dec_len，在遍历过程中更新长度。
  • 只需 O(n) 的时间复杂度即可求解。
  • 适用于 任意整数数组，不会受到数值范围的影响。

这种方法简单且高效，适用于大规模数据集。🚀