2024-11-24：最长的严格递增或递减子数组。用go语言，给定一个整数数组 nums，请找出其中最长的严格递增或严格递减的非

2024-11-24：最长的严格递增或递减子数组。用go语言，给定一个整数数组 nums，请找出其中最长的严格递增或严格递减的非空子数组的长度并返回。

输入：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 。

答案2024-11-24：

chatgpt[1]

题目来自leetcode3105。

大体步骤如下：

1.初始化变量：

• 创建一个变量ans，用于存储当前找到的最长递增或递减子数组的长度，初始值设为 0。

• 获取输入数组的长度n。

2.外层循环：

• 从数组的第一个元素开始，使用一个外层循环遍历数组中的每个元素，索引为i。外层循环的范围是从 0 到n-1。

3.内层循环初始化：

• 对于每个i，初始化两个计数器upper和down，分别用于跟踪当前找到的严格递增和严格递减子数组的长度。两者的初始值设置为 1，表示当前索引的元素本身。

4.检查严格递增子数组：

4.1.在内层循环中，从j = i + 1开始，遍历数组的后续元素。4.2.检查nums[j-1]和nums[j]：4.2.1.如果两个相邻元素相等（nums[j-1] == nums[j]），则表明不能继续扩展递增或递减子数组，跳出内层循环。4.2.2.如果前一个元素小于当前元素（nums[j-1] < nums[j]），表明当前子数组可以继续严格递增。此时，检查down是否为 1（表示当前不是在递减子数组中），如果是，那么就可以将upper增加 1。4.2.3.如果前一个元素大于当前元素（nums[j-1] > nums[j]），则说明无法继续扩展递增数组，此时该部分内层循环将用于检查递减子数组。

5.检查严格递减子数组：

• 类似地，如果nums[j-1] > nums[j]，则检查upper是否为 1（表示当前不是在递增子数组中），如果是，那么就可以将down增加 1。

6.更新结果：

• 在内层循环结束后，检查upper和down中的值。

• 使用ans = max(ans, upper)更新ans为当前找到的最长严格递增子数组和ans的最大值。

• 使用ans = max(ans, down)更新ans为当前找到的最长严格递减子数组和ans的最大值。

7.返回结果：

• 当外层循环结束后，返回ans，这时ans包含了所有可能的严格递增或递减子数组中的最大长度。

时间复杂度分析

•时间复杂度：O(n²)

• 外层循环遍历n个元素，每个元素可能需要通过内层循环遍历后续的 (最坏情况下) n-1 个元素。因此，在最坏情况下，整体的时间复杂度为 O(n) * O(n) = O(n²)。

空间复杂度分析

•空间复杂度：O(1)

• 除了输入数组本身，算法中仅使用了几个额外的变量 (ans,n,upper,down)，这些变量的空间占用是常量级别的。所以空间复杂度为 O(1)。

Go完整代码如下：

package main

import"fmt"

func longestMonotonicSubarray(nums []int)int{

ans :=0

n :=len(nums)

for i :=0; i < n; i++{

upper, down :=1,1

for j := i +1; j < n; j++{

if nums[j-1]== nums[j]{

break

}

if nums[j-1]< nums[j]{

if down !=1{

break

}

upper++

}else{

if upper !=1{

break

}

down++

}

}

if upper > ans {

ans = upper

}

if down > ans {

ans = down

}

}

return ans

}

func main(){

nums :=[]int{1,4,3,3,2}

result := longestMonotonicSubarray(nums)

fmt.Println(result)

}

Rust完整代码如下：

fn longest_monotonic_subarray(nums:Vec<i32>)->i32{

letmut ans=0;

letn= nums.len();

foriin0..n {

letmut upper=1;

letmut down=1;

forjin i +1..n {

if nums[j -1]== nums[j]{

break;

}

if nums[j -1]< nums[j]{

if down !=1{

break;

}

upper +=1;

}else{

if upper !=1{

break;

}

down +=1;

}

}

if upper > ans {

ans = upper;

}

if down > ans {

ans = down;

}

}

ans

}

fnmain(){

letnums=vec![1,4,3,3,2];

letresult=longest_monotonic_subarray(nums);

println!("{}", result);

}

引用链接