技术标签: 算法 leetcode 动态规划 数据结构 LeetCode
当 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
法一:滑动窗口
代码一:
int odd(int* arr, int arrSize, int left, int right){
int maxLen = 1;
while(right < arrSize - 1){
//k为奇数位
if (right % 2 == 1 && arr[right] > arr[right + 1]){
right++;
continue;
}
//且对应偶数位
if (right % 2 == 0 && arr[right] < arr[right + 1]){
right++;
continue;
}
//发现不符合情况,获取最大长度
maxLen = fmax(maxLen,right - left + 1);
//移动
right++;
left = right;//重新定义左边界
}
maxLen = fmax(maxLen,right - left + 1);//循环外也得有一层最大长度获取
return maxLen;
}
int even(int* arr, int arrSize, int left, int right){
int maxLen = 1;
while(right < arrSize - 1){
//k为偶数位
if (right % 2 == 0 && arr[right] > arr[right + 1]){
right++;
continue;
}
//且对应奇数位
if (right % 2 == 1 && arr[right] < arr[right + 1]){
right++;
continue;
}
//发现不符合情况,获取最大长度
maxLen = fmax(maxLen,right - left + 1);
//移动
right++;
left = right;//重新定义左边界
}
maxLen = fmax(maxLen,right - left + 1);//循环外也得有一层最大长度获取
return maxLen;
}
int maxTurbulenceSize(int* arr, int arrSize){
int ret = 1, left = 0, right = 0;
ret = fmax(odd(arr,arrSize,left,right),even(arr,arrSize,left,right));//根据k的奇偶来获取最大值
return ret;
}
代码二:
int maxTurbulenceSize(int* arr, int arrSize){
int ret = 1;
int left = 0, right = 0;
while (right < arrSize - 1){
if (left == right){
//窗口为1
if (arr[left] == arr[left + 1]){
left++;
}
right++;
}
else{
//窗口不为1,当前窗口[left,right],满足湍流子数组判断条件
//right能否右移看是否满足湍流子数组判断条件
if (arr[right - 1] > arr[right] && arr[right] < arr[right + 1]){
right++;
} else if (arr[right - 1] < arr[right] && arr[right] > arr[right + 1]){
right++;
} else {
//不满足条件说明,[left,right + 1]无法构成湍流子数组,我们改变窗口
left = right;
}
}
ret = fmax(ret, right - left + 1);
}
return ret;
}
法二:动态规划
int maxTurbulenceSize(int* arr, int arrSize){
int dp[arrSize][2];
//i > 0,当arr[i - 1] = arr[i]以i结尾的湍流子数组长度为1,
for (int i = 0; i < arrSize; i++) {
dp[i][0] = dp[i][1] = 1;
}
//当arr[i - 1] != arr[i]
for (int i = 1; i < arrSize; i++) {
if (arr[i - 1] > arr[i]) {
dp[i][0] = dp[i - 1][1] + 1;//dp[i - 1][1]-->将arr[i - 1] > arr[i - 2]状态添加进去
} else if (arr[i - 1] < arr[i]) {
dp[i][1] = dp[i - 1][0] + 1;//dp[i - 1][0]-->将arr[i - 2] > arr[i - 1]状态添加进去
}
}
int ret = 1;
//结果出现在两种状态下的湍流子数组中
for (int i = 0; i < arrSize; i++) {
ret = fmax(ret, dp[i][0]);
ret = fmax(ret, dp[i][1]);
}
return ret;
}
法三:滚动数组
int maxTurbulenceSize(int* arr, int arrSize){
int ret = 1;
int dp0 = 1, dp1 = 1;
for (int i = 1; i < arrSize; i++) {
if (arr[i - 1] > arr[i]) {
dp0 = dp1 + 1;//满足if了
dp1 = 1;//那么肯定不满足arr[i - 1] < arr[i]所以dp1只能为1,下同理
} else if (arr[i - 1] < arr[i]) {
dp1 = dp0 + 1;
dp0 = 1;
} else {
dp0 = 1;
dp1 = 1;
}
ret = fmax(ret, dp0);
ret = fmax(ret, dp1);
}
return ret;
}
文章浏览阅读2.9k次,点赞8次,收藏14次。测试主要做什么?这完全都体现在测试流程中,同时测试流程是面试问题中出现频率最高的,这不仅是因为测试流程很重要,而是在面试过程中这短短的半小时到一个小时的时间,通过测试流程就可以判断出应聘者是否合适,故在测试流程中包含了测试工作的核心内容,例如需求分析,测试用例的设计,测试执行,缺陷等重要的过程。..._测试过程管理中包含哪些过程
文章浏览阅读870次,点赞16次,收藏19次。1.背景介绍政府数字化政务是指政府利用数字技术、互联网、大数据、人工智能等新技术手段,对政府政务进行数字化改革,提高政府工作效率,提升政府服务质量的过程。随着人工智能(AI)和机器学习(ML)技术的快速发展,政府数字化政务中的人工智能与机器学习应用也逐渐成为政府改革的重要内容。政府数字化政务的人工智能与机器学习应用涉及多个领域,包括政策决策、政府服务、公共安全、社会治理等。在这些领域,人工...
文章浏览阅读219次,点赞2次,收藏4次。系统主要的用户为用户、管理员,他们的具体权限如下:用户:用户登录后可以对管理员上传的学习视频进行学习。用户可以选择题型进行练习。用户选择小程序提供的考研科目进行相关训练。用户可以进行水平测试,并且查看相关成绩用户可以进行错题集的整理管理员:管理员登录后可管理个人基本信息管理员登录后可管理个人基本信息管理员可以上传、发布考研的相关例题及其分析,并对题型进行管理管理员可以进行查看、搜索考研题目及错题情况。_mysql刷题软件
文章浏览阅读1.4k次。myelipse里有UML1和UML2两种方式,UML2功能更强大,但是两者生成过程差别不大1.建立Test工程,如下图,uml包存放uml类图package com.zz.domain;public class User {private int id;private String name;public int getId() {return id;}public void setId(int..._根据以下java代码画出类图
文章浏览阅读174次。需求:一个topic包含很多个表信息,需要自动根据json字符串中的字段来写入到hive不同的表对应的路径中。发送到Kafka中的数据原本最外层原本没有pkDay和project,只有data和name。因为担心data里面会空值,所以根同事商量,让他们在最外层添加了project和pkDay字段。pkDay字段用于表的自动分区,proejct和name合起来用于自动拼接hive表的名称为 ..._flume拦截器自定义开发 kafka
文章浏览阅读380次。原标题:Java Spring中同时访问多种不同数据库 多样的工作要求,可以使用不同的工作方法,只要能获得结果,就不会徒劳。开发企业应用时我们常常遇到要同时访问多种不同数据库的问题,有时是必须把数据归档到某种数据仓库中,有时是要把数据变更推送到第三方数据库中。使用Spring框架时,使用单一数据库是非常容易的,但如果要同时访问多个数据库的话事件就变得复杂多了。本文以在Spring框架下开发一个Sp..._根据输入的不同连接不同的数据库
文章浏览阅读3.6k次,点赞9次,收藏25次。本案例描述了晶振屏蔽以及开关电源变压器屏蔽对系统稳定工作的影响, 硬件设计时应考虑。_eft电路图
文章浏览阅读1.1k次。对于物料价格的更改,可以采取不同的手段:首先,我们来介绍MR21的方式。 需要说明的是,如果要对某一产品进行价格修改,必须满足的前提条件是: ■ 1、必须对价格生效的物料期间与对应会计期间进行开启; ■ 2、该产品在该物料期间未发生物料移动。执行MR21,例如更改物料1180051689的价格为20000元,系统提示“对于物料1180051689 存在一个当前或未来标准价格”,这是因为已经对该..._mr21 对于物料 zba89121 存在一个当前或未来标准价格
文章浏览阅读7.4k次,点赞3次,收藏13次。[文章导读]联想启天M420是一款商用台式电脑,预装的是win10系统,用户还是喜欢win7系统,该台式机采用的intel 8代i5 8500CPU,在安装安装win7时有很多问题,在安装win7时要在BIOS中“关闭安全启动”和“开启兼容模式”,并且安装过程中usb不能使用,要采用联想win7新机型安装,且默认采用的uefi+gpt模式,要改成legacy+mbr引导,那么联想启天M420台式电..._启天m420刷bios
文章浏览阅读2.7k次,点赞2次,收藏9次。一,为什么要冗余数据互联网数据量很大的业务场景,往往数据库需要进行水平切分来降低单库数据量。水平切分会有一个patition key,通过patition key的查询能..._保证冗余性
文章浏览阅读88次。是时候闭环Java应用了 原创 2016-08-16 张开涛 你曾经因为部署/上线而痛苦吗?你曾经因为要去运维那改配置而烦恼吗?在我接触过的一些部署/上线方式中,曾碰到过以下一些问题:1、程序代码和依赖都是人工上传到服务器,不是通过工具进行部署和发布;2、目录结构没有规范,jar启动时通过-classpath任意指定;3、fat jar,把程序代码、配置文件和依赖jar都打包到一个jar中,改配置..._那么需要把上面的defaultjavatyperesolver类打包到插件中
文章浏览阅读909次。1.得下载一个番茄插件,按alt+g才可以有函数跳转功能。2.不安装番茄插件,按F12也可以有跳转功能。3.进公司的VS工程是D:\sync\build\win路径,.sln才是打开工程的方式,一个是VS2005打开的,一个是VS2013打开的。4.公司库里的线程接口,在CmThreadManager.h 里,这个里面是我们的线程库,可以直接拿来用。CreateUserTaskThre..._番茄助手颜色