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

最长严格递增或严格递减子数组问题用于查找给定数组中连续子数组的最大长度，其中元素严格递增或严格递减。

问题陈述

给定一个整数数组 nums，返回长度为 n 的最长子数组，该子数组要么严格递增，要么严格递减。

示例场景 1

Input: nums = [1, 3, 2, 4, 3, 5, 4, 6]
Output: n = 2

最长的严格递增子数组是 [1, 3]、[2, 4]、[3, 5] 和 [4, 6]。最长的严格递减子数组是 [3, 2] 和 [4, 3]。最长子数组 = [1, 3]、[2, 4]、[3, 5] 或 [4, 6]，每个长度为 2。

示例场景 2

Input: nums = [5, 4, 3, 2, 1]
Output: n = 5

整个数组严格递减，因此最长子数组 = [5, 4, 3, 2, 1]，长度为 5。

示例场景 3

Input: nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Output: n = 10

整个数组严格递增，因此最长子数组 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]，长度为 10。

示例场景 4

Input: nums = [10, 20, 30, 25, 20, 15]
Output: n = 4

最长的严格递增子数组 = [10, 20, 30]，最长的严格递减子数组 = [30, 25, 20, 15]。最长子数组 = [30, 25, 20, 15]，长度为 4。

时间复杂度

计算字符串分数的时间复杂度为 O(n)，其中 n 是字符串的最大长度。

要使用各种编程语言解决此问题，请使用以下方法。
  • 线性扫描方法
  • 两遍扫描方法

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

线性扫描方法

此方法涉及对数组进行单次遍历以跟踪当前递增或递减子数组的长度并更新最大长度。

示例

C++ Java Python
Open Compiler
#include <iostream>
#include <vector>
using namespace std;

int longestSubarray(vector<int>& nums) {
   int n = nums.size();
   if (n == 0) return 0;

   int maxLength = 1, incLength = 1, decLength = 1;

   for (int i = 1; i < n; ++i) {
      if (nums[i] > nums[i - 1]) {
         incLength++;
         decLength = 1;
      } else if (nums[i] < nums[i - 1]) {
         decLength++;
         incLength = 1;
      } else {
         incLength = 1;
         decLength = 1;
      }
      maxLength = max(maxLength, max(incLength, decLength));
   }

   return maxLength;
}

int main() {
   vector<int> nums = {10, 20, 30, 25, 20, 15};
   cout << "Length of the longest subarray = " << longestSubarray(nums) << endl;
   return 0;
}

输出

Length of the longest subarray =  4
Open Compiler
public class LongestSubarray {
   public static int longestSubarray(int[] nums) {
      int n = nums.length;
      if (n == 0) return 0;
   
      int maxLength = 1, incLength = 1, decLength = 1;
   
      for (int i = 1; i < n; ++i) {
         if (nums[i] > nums[i - 1]) {
            incLength++;
            decLength = 1;
         } else if (nums[i] < nums[i - 1]) {
            decLength++;
            incLength = 1;
         } else {
            incLength = 1;
            decLength = 1;
         }
         maxLength = Math.max(maxLength, Math.max(incLength, decLength));
      }
   
      return maxLength;
   }
   
   public static void main(String[] args) {
      int[] nums = {10, 20, 30, 25, 20, 15};
      System.out.println("Length of the longest subarray = " + longestSubarray(nums));
   }
}

输出

Length of the longest subarray = 4
Open Compiler
def longest_subarray(nums):
   n = len(nums)
   if n == 0:
       return 0

   max_length = 1
   inc_length = 1
   dec_length = 1

   for i in range(1, n):
      if nums[i] > nums[i - 1]:
         inc_length += 1
         dec_length = 1
      elif nums[i] < nums[i - 1]:
         dec_length += 1
         inc_length = 1
      else:
         inc_length = 1
         dec_length = 1
      max_length = max(max_length, inc_length, dec_length)

   return max_length

# Example usage
nums = [10, 20, 30, 25, 20, 15]
print("Length of the longest subarray = ", longest_subarray(nums))

输出

Length of the longest subarray = 4

两遍扫描方法

在此方法中，我们可以对数组执行两次单独的遍历。第一次遍历查找最长严格递增子数组的长度，第二次遍历查找最长严格递减子数组的长度。因此，您可以根据此计算两个长度中的最大值。

示例

C++ Java Python
Open Compiler
#include <iostream>
#include <vector>
using namespace std;

int longestIncreasingSubarray(vector<int>& nums) {
   int maxLength = 1, currentLength = 1;
   for (int i = 1; i < nums.size(); ++i) {
      if (nums[i] > nums[i - 1]) {
         currentLength++;
      } else {
         currentLength = 1;
      }
      maxLength = max(maxLength, currentLength);
   }
   return maxLength;
}

int longestDecreasingSubarray(vector<int>& nums) {
   int maxLength = 1, currentLength = 1;
   for (int i = 1; i < nums.size(); ++i) {
      if (nums[i] < nums[i - 1]) {
         currentLength++;
      } else {
         currentLength = 1;
      }
      maxLength = max(maxLength, currentLength);
   }
   return maxLength;
}

int longestSubarray(vector<int>& nums) {
   return max(longestIncreasingSubarray(nums), longestDecreasingSubarray(nums));
}

int main() {
   vector<int> nums = {10, 20, 30, 25, 20, 15};
   cout << "Length of the longest subarray = " << longestSubarray(nums) << endl;
   return 0;
}

输出

Length of the longest subarray =  4
Open Compiler
public class LongestSubarray {
   public static int longestIncreasingSubarray(int[] nums) {
      int maxLength = 1, currentLength = 1;
      for (int i = 1; i < nums.length; ++i) {
         if (nums[i] > nums[i - 1]) {
            currentLength++;
         } else {
            currentLength = 1;
         }
         maxLength = Math.max(maxLength, currentLength);
      }
      return maxLength;
   }
   
   public static int longestDecreasingSubarray(int[] nums) {
      int maxLength = 1, currentLength = 1;
      for (int i = 1; i < nums.length; ++i) {
         if (nums[i] < nums[i - 1]) {
            currentLength++;
         } else {
            currentLength = 1;
         }
         maxLength = Math.max(maxLength, currentLength);
      }
      return maxLength;
   }
   
   public static int longestSubarray(int[] nums) {
      return Math.max(longestIncreasingSubarray(nums), longestDecreasingSubarray(nums));
   }
   
   public static void main(String[] args) {
      int[] nums = {10, 20, 30, 25, 20, 15};
      System.out.println("Length of the longest subarray = " + longestSubarray(nums));
   }
}

输出

Length of the longest subarray =  4
Open Compiler
def longest_increasing_subarray(nums):
   max_length = 1
   current_length = 1
   for i in range(1, len(nums)):
      if nums[i] > nums[i - 1]:
          current_length += 1
      else:
          current_length = 1
      max_length = max(max_length, current_length)
   return max_length

def longest_decreasing_subarray(nums):
   max_length = 1
   current_length = 1
   for i in range(1, len(nums)):
      if nums[i] < nums[i - 1]:
         current_length += 1
      else:
         current_length = 1
      max_length = max(max_length, current_length)
   return max_length

def longest_subarray(nums):
   return max(longest_increasing_subarray(nums), longest_decreasing_subarray(nums))

# Example usage
nums = [10, 20, 30, 25, 20, 15]
print("Length of the longest subarray = ", longest_subarray(nums))

输出

Length of the longest subarray =  4

Revathi Satya Kondra
Revathi Satya Kondra

Tutorialspoint 技术内容撰写人

更新于: 2024年7月23日

184 次查看

开始你的 职业生涯

通过完成课程获得认证

开始
广告