3105. Longest Strictly Increasing or Strictly Decreasing Subarray

Problem

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.

A subarray is a contiguous non-empty sequence of elements within an array.

An array is said to be strictly increasing if each element is strictly greater than its previous one (if exists).

An array is said to be strictly decreasing if each element is strictly smaller than its previous one (if exists).

https://leetcode.com/problems/longest-strictly-increasing-or-strictly-decreasing-subarray/

Example 1:

Input: nums = [1,4,3,3,2]
Output: 2
Explanation:
The strictly increasing subarrays of nums are [1], [2], [3], [3], [4], and [1,4].
The strictly decreasing subarrays of nums are [1], [2], [3], [3], [4], [3,2], and [4,3].
Hence, we return 2.

Example 2:

Input: nums = [3,3,3,3]
Output: 1
Explanation:
The strictly increasing subarrays of nums are [3], [3], [3], and [3].
The strictly decreasing subarrays of nums are [3], [3], [3], and [3].
Hence, we return 1.

Example 3:

Input: nums = [3,2,1]
Output: 3
Explanation:
The strictly increasing subarrays of nums are [3], [2], and [1].
The strictly decreasing subarrays of nums are [3], [2], [1], [3,2], [2,1], and [3,2,1].
Hence, we return 3.

Constraints:

• 1 <= nums.length <= 50
• 1 <= nums[i] <= 50

Test Cases

1
2

class Solution:
    def longestMonotonicSubarray(self, nums: List[int]) -> int:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

import pytest

from solution import Solution


@pytest.mark.parametrize('nums, expected', [
    ([1,4,3,3,2], 2),
    ([3,3,3,3], 1),
    ([3,2,1], 3),

    ([1,9,7,1], 3),
])
@pytest.mark.parametrize('sol', [Solution()])
def test_solution(sol, nums, expected):
    assert sol.longestMonotonicSubarray(nums) == expected

Thoughts

一个直观的思路是先统计 nums 中最长的严格递增子数组的长度，再统计最长的严格递减子数组的长度，二者取较大的。也可以在一次循环里完成，增加一个状态记录当前是在严格递增子数组中还是严格递减子数组中。

时间复杂度 O(n)，空间复杂度 O(1)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def longestMonotonicSubarray(self, nums: list[int]) -> int:
        max2 = lambda a, b: a if a >= b else b
        longest = 0
        current = 0
        dir = 0
        prev = nums[0]
        for num in nums:
            if num == prev:
                current = 1
                dir = 0
            elif num > prev:
                current = current + 1 if dir >= 0 else 2
                dir = 1
            else:
                current = current + 1 if dir <= 0 else 2
                dir = -1

            longest = max2(longest, current)
            prev = num

        return longest

许可协议

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

分享文章