您现在的位置是:首页 > 正文

LeetCode——978. 最长湍流子数组(Longest Turbulent Subarray)——分析及代码(Java)

2024-01-30 22:14:22阅读 0

一、题目

当 A 的子数组 A[i], A[i+1], …, A[j] 满足下列条件时,我们称其为湍流子数组:

  • 若 i <= k < j,当 k 为奇数时,A[k] > A[k+1],且当 k 为偶数时,A[k] < A[k+1];
  • 或 若 i <= k < j,当 k 为偶数时,A[k] > A[k+1] ,且当 k 为奇数时,A[k] < A[k+1]。

也就是说,如果比较符号在子数组中的每个相邻元素对之间翻转,则该子数组是湍流子数组。
返回 A 的最大湍流子数组的长度。

示例 1:

输入:[9,4,2,10,7,8,8,1,9]
输出:5
解释:(A[1] > A[2] < A[3] > A[4] < A[5])

示例 2:

输入:[4,8,12,16]
输出:2

示例 3:

输入:[100]
输出:1

提示:

  • 1 <= A.length <= 40000
  • 0 <= A[i] <= 10^9

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-turbulent-subarray
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

二、分析及代码

1. 动态规划(一维数组)

(1)思路

设计一个数组 dp[n],表示到第 i 个数字时当前湍流子数组的长度,则状态转移过程为:

  • 若当前数字与前一数字相等,dp[i] = 1
  • 若当前数字符合湍流数组要求,dp[i] = dp[i - 1] + 1
  • 若当前数字与前一数字不相等但不符合湍流数组要求,dp[i] = 2

dp[i] 的最大值即为目标解。

(2)代码

class Solution {
    public int maxTurbulenceSize(int[] arr) {
        if (arr.length == 1)
            return 1;
        int[] dp = new int[arr.length];//dp[i]表示到第i个数字时当前湍流子数组的长度
        dp[0] = 1;
        dp[1] = (arr[0] == arr[1]) ? 1 : 2;
        int n = arr.length, ans = dp[1];
        for (int i = 2; i < n; i++) {
            if (arr[i] == arr[i - 1])
                dp[i] = 1;
            else if ((arr[i] > arr[i - 1] && arr[i - 1] < arr[i - 2]) || (arr[i] < arr[i - 1] && arr[i - 1] > arr[i - 2])) {
                dp[i] = dp[i - 1] + 1;
                ans = Math.max(ans, dp[i]);
            } else
                dp[i] = 2;
        }
        return ans;
    }
}

(3)结果

执行用时 :6 ms,在所有 Java 提交中击败了 87.95% 的用户;
内存消耗 :45.1 MB,在所有 Java 提交中击败了 7.72% 的用户。

2. 动态规划(单个数字)

(1)思路

上述方法计算过程中,dp[i] 的状态只与 dp[i - 1] 有关,因此可直接用一个整数替代一维数组。

(2)代码

class Solution {
    public int maxTurbulenceSize(int[] arr) {
        if (arr.length == 1)
            return 1;
        int len = (arr[0] == arr[1]) ? 1 : 2;
        int n = arr.length, ans = len;
        for (int i = 2; i < n; i++) {
            if (arr[i] == arr[i - 1])
                len = 1;
            else if ((arr[i] > arr[i - 1] && arr[i - 1] < arr[i - 2]) || (arr[i] < arr[i - 1] && arr[i - 1] > arr[i - 2])) {
                len++;
                ans = Math.max(ans, len);
            } else
                len = 2;
        }
        return ans;
    }
}

(3)结果

执行用时 :6 ms,在所有 Java 提交中击败了 78.92% 的用户;
内存消耗 :41.8 MB,在所有 Java 提交中击败了 56.40% 的用户。

三、其他

暂无。

网站文章

  • Java项目:在线点餐系统(java+SSM+jsp+mysql+maven)

    Java项目:在线点餐系统(java+SSM+jsp+mysql+maven)

    一、项目简述功能包括: 在线点餐,评论,购物车,下单,支付,管理员,店家多 商家管理,后台评论管理,订单管理,商品管理等等。二、项目运行环境配置: Jdk1.8 + Tomcat8.5 + mysql...

    2024-01-30 22:13:46
  • android 20,Android第二十六天

    一:反射机制通过对象获取它所属的类。反射机制的源头是Class类。Class类Class类的实例表示正在运行的Java应用程序中的类和接口。二:获取Class类的实例的三种方法:1. Class.forName("xxx.xxx.类名");2. getClass() 返回运行时类3. 类.class (Android中经常会用到)三:Class类的常用方法:1.public Field[] ...

    2024-01-30 22:13:39
  • MysqlCluster集群搭建及使用

    MysqlCluster集群搭建及使用

    亿级用户的分布式数据存储解决方案 1文章目录1、简介2、搭建Mysql Cluster(基于阿里云内网部署,相同实例地区)2.1 安装配置管理节点(GMG)2.2 安装配置数据节点(NDB)2.3 安...

    2024-01-30 22:13:33
  • requests请求库

    requests请求库

    一、介绍 #介绍:使用requests可以模拟浏览器的请求,比起之前用到的urllib,requests模块的api更加便捷(本质就是封装了urllib3) #注意:requests库发送请求将网页内容下载下来以后,并不会执行js代码,这需要我们自己分析目标站点然后发起新的request请求 #安装:pip3 install requests #各种请求方式:常用...

    2024-01-30 22:13:05
  • 计算机软件可专利性否定,什么是计算机软件可专利性?计算机软件的专利保护有什么特点?...

    计算机软件的专利保护有什么特点?计算机软件可专利性,是指软件属于应当被授予专利的发明创造。计算机软件作为信息产业的支柱之一,对其进行制度保护是必要的。专利法上所称发明是指对产品、方法或者其改进所提出新...

    2024-01-30 22:13:00
  • vue+elementUi发送邮件组件编写

    vue+elementUi发送邮件组件编写

    父组件:<email-dialog v-if="showemailDialog" v-on:closeemailDialog="closeemailDialog" :multipleSelectio...

    2024-01-30 22:12:53
  • Sentinel+Nacos+SpringCloud流量控制实现

    Sentinel+Nacos+SpringCloud流量控制实现

    环境说明: Sentinel-1.6.0 Nacos-1.0.0 1.pom.xml配置 org.springframework.boot spring-boot-starter-parent...

    2024-01-30 22:12:46
  • Qt-QPixmap

    Qt-QPixmap

    2024-01-30 22:12:16
  • Mongo String类型日期转ISODate类型

    在mysql数据库导出的csv文件里的数据导入到mongodb数据库中, 发现日期数据是String,想要专为mongo的ISODate,方便以后的关于时间的查询。 以users表为例 方法一:少量数...

    2024-01-30 22:12:07
  • 定义可变参数的宏

    定义可变参数的宏

    像printf类的函数,如果代码中的比较多,且需要检查返回值时,没用到一个地方就添加一段返回值检查会比较烦,不添加,如果要求pclint扫描时会报warning 514。 为了方便,有两种方式,一种是...

    2024-01-30 22:11:59