What is the primary pattern for solving the Longest Strictly Increasing or Strictly Decreasing Subarray problem?

The primary pattern is an array-driven solution that involves scanning through the array and tracking strictly increasing and decreasing subarrays.

What is the time complexity of the Longest Strictly Increasing or Strictly Decreasing Subarray problem?

The time complexity is O(n), where n is the length of the array, as we only need to iterate through it once.

How do we handle equal consecutive elements in the array?

Equal consecutive elements break both increasing and decreasing sequences, so the current sequence length must be reset whenever they are encountered.

What are common edge cases for the Longest Strictly Increasing or Strictly Decreasing Subarray problem?

Edge cases include arrays with all equal elements, arrays of length 1, and arrays that are already strictly increasing or decreasing.

What would be a more efficient solution if space complexity were not a constraint?

If space complexity were not a constraint, a dynamic programming approach could be used, but it would increase the space complexity to O(n).

#3105

Easy

auto_awesome数组·driven

LeetCode 题解工作台

最长的严格递增或递减子数组

给你一个整数数组 nums 。返回数组 nums 中严格递增或严格递减的最长非空子数组的长度。示例 1：输入： nums = [1,4,3,3,2] 输出： 2 解释： nums 中严格递增的子数组有 [1] 、 [2] 、 [3] 、 [3] 、 [4] 以及 [1,4] 。 num…

数组

题目描述

给你一个整数数组 nums 。

返回数组 nums 中 严格递增 或 严格递减 的最长非空子数组的长度。

示例 1：

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

输出：2

解释：

nums 中严格递增的子数组有[1]、[2]、[3]、[3]、[4] 以及 [1,4] 。

nums 中严格递减的子数组有[1]、[2]、[3]、[3]、[4]、[3,2] 以及 [4,3] 。

因此，返回 2 。

示例 2：

输入：nums = [3,3,3,3]

输出：1

解释：

nums 中严格递增的子数组有 [3]、[3]、[3] 以及 [3] 。

nums 中严格递减的子数组有 [3]、[3]、[3] 以及 [3] 。

因此，返回 1 。

示例 3：

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

输出：3

解释：

nums 中严格递增的子数组有 [3]、[2] 以及 [1] 。

nums 中严格递减的子数组有 [3]、[2]、[1]、[3,2]、[2,1] 以及 [3,2,1] 。

因此，返回 3 。

提示：

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

lightbulb

解题思路

方法一：两次遍历

我们先进行一次遍历，找出严格递增的最长子数组长度，更新答案。然后再进行一次遍历，找出严格递减的最长子数组长度，再次更新答案。

时间复杂度 $O(n)$ ，其中 $n$ 是数组的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def longestMonotonicSubarray(self, nums: List[int]) -> int:
        ans = t = 1
        for i, x in enumerate(nums[1:]):
            if nums[i] < x:
                t += 1
                ans = max(ans, t)
            else:
                t = 1
        t = 1
        for i, x in enumerate(nums[1:]):
            if nums[i] > x:
                t += 1
                ans = max(ans, t)
            else:
                t = 1
        return ans

speed

复杂度分析

指标	值
时间	O(n)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate efficiently track and compare sequence lengths during iteration?
question_mark
Does the candidate correctly identify when to reset sequence tracking?
question_mark
How well does the candidate handle edge cases, such as arrays with all equal elements?

warning

常见陷阱

外企场景

error
Failing to track both increasing and decreasing sequences separately.
error
Incorrectly updating the maximum length during iteration.
error
Not resetting sequence lengths at the right points when the array changes direction.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the array contains only one element?
arrow_right_alt
How would the solution change if we had to return the subarray itself rather than just the length?
arrow_right_alt
Can this problem be solved with dynamic programming, and what would be the trade-off?

help

常见问题

外企场景

继续练习

#3107 使数组中位数等于 K 的最少操作数 #3102 最小化曼哈顿距离 #3108 带权图里旅途的最小代价