数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究最长严格递增或严格递减子数组
最长严格递增或严格递减子数组问题用于查找给定数组中连续子数组的最大长度，其中元素严格递增或严格递减。
问题陈述
给定一个整数数组 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 是字符串的最大长度。
要使用各种编程语言解决此问题，请使用以下方法。
- 线性扫描方法
- 两遍扫描方法
线性扫描方法
此方法涉及对数组进行单次遍历以跟踪当前递增或递减子数组的长度并更新最大长度。
示例
#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
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
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
两遍扫描方法
在此方法中，我们可以对数组执行两次单独的遍历。第一次遍历查找最长严格递增子数组的长度，第二次遍历查找最长严格递减子数组的长度。因此，您可以根据此计算两个长度中的最大值。
示例
#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
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
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
更新于: 2024年7月23日
184 次查看
广告