資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
廣告