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);
}

引用链接

[1] chatgpt: https://chatbotsplace.com/?rc=nnNWSCJ7EP