Easy

题目描述

给你一个整数数组 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

解题思路

这道题要求找到最长的严格递增或严格递减子数组。我们可以使用一次遍历的方法来解决。

核心思路是分别维护两个变量：当前严格递增子数组的长度和当前严格递减子数组的长度。遍历数组时，比较相邻元素：

  • 如果当前元素大于前一个元素，说明可以继续递增序列，递增长度加1，递减长度重置为1
  • 如果当前元素小于前一个元素，说明可以继续递减序列，递减长度加1，递增长度重置为1
  • 如果当前元素等于前一个元素，两个长度都重置为1

在遍历过程中，我们持续更新最大长度。这种方法的时间复杂度为O(n)，空间复杂度为O(1)。

另一种思路是暴力枚举所有子数组并检查其单调性，但时间复杂度为O(n³)，不够高效。对于这道题的数据规模，一次遍历的贪心方法是最优解。

代码实现

class Solution {
public:
    int longestMonotonicSubarray(vector<int>& nums) {
        int n = nums.size();
        if (n <= 1) return n;
        
        int maxLen = 1;
        int incLen = 1, decLen = 1;
        
        for (int i = 1; i < n; i++) {
            if (nums[i] > nums[i-1]) {
                incLen++;
                decLen = 1;
            } else if (nums[i] < nums[i-1]) {
                decLen++;
                incLen = 1;
            } else {
                incLen = 1;
                decLen = 1;
            }
            maxLen = max(maxLen, max(incLen, decLen));
        }
        
        return maxLen;
    }
};

class Solution:
    def longestMonotonicSubarray(self, nums: List[int]) -> int:
        n = len(nums)
        if n <= 1:
            return n
        
        max_len = 1
        inc_len = dec_len = 1
        
        for i in range(1, n):
            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

public class Solution {
    public int LongestMonotonicSubarray(int[] nums) {
        int n = nums.Length;
        if (n <= 1) return n;
        
        int maxLen = 1;
        int incLen = 1, decLen = 1;
        
        for (int i = 1; i < n; i++) {
            if (nums[i] > nums[i-1]) {
                incLen++;
                decLen = 1;
            } else if (nums[i] < nums[i-1]) {
                decLen++;
                incLen = 1;
            } else {
                incLen = 1;
                decLen = 1;
            }
            maxLen = Math.Max(maxLen, Math.Max(incLen, decLen));
        }
        
        return maxLen;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestMonotonicSubarray = function(nums) {
    const n = nums.length;
    if (n <= 1) return n;
    
    let maxLen = 1;
    let incLen = 1, decLen = 1;
    
    for (let i = 1; i < n; i++) {
        if (nums[i] > nums[i-1]) {
            incLen++;
            decLen = 1;
        } else if (nums[i] < nums[i-1]) {
            decLen++;
            incLen = 1;
        } else {
            incLen = 1;
            decLen = 1;
        }
        maxLen = Math.max(maxLen, incLen, decLen);
    }
    
    return maxLen;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n)
空间复杂度O(1)