小森家的北面有一条连绵的山脉,山脉高低起伏。小森很好奇这些山中最多有几座连续的山头是越来越高的,当然这对小森来说太简单了。他又想,假如可以移除其中一座,这个答案最大又会是多少?当然了,他也可以选择不移除任何一座山峰。1<=n<=100000, 1<=a[i] <=1000000000。输入内容为两行,第一行为山峰的数量n,第二行为n个数字,表示每个山头的高度。输出一个数字,表示最大值。
初始化两个数组,oneIndex 和 arr,arr保存当前增区间的长度,oneIndex保存arr中数组元素为1的索引位置,对于[5,10,6,7,8]例子,arr={1,2,1,2,3}(5,10 递增,6,7,8 为一个增区间 ),oneIndex={0,2}(因为 arr[0]=1,arr[2]=1)。这下明白这两个数组的含义了吧。接下来遍历oneIndex区间,也就是找出arr中所有为1的值的索引(arr数组的存在可以不用遍历 arr 找 1 的位置,而是可以直接定位,用空间换时间 )所有为 1 的值的索引的元素 ( 除第一个 1)和其前面的那个元素都有移除的嫌疑,移除后计算长度。先移除 1 前面那座山,也就是上一个区间最高的山。 再移除 1 这座山,也就是当前区间最低的山 ( 有同学可以不明白为什么最低的山 也有移除的可能性 , 看看下面的例子 )
可能出现这种情况
这样的话,即使 3 是第二个区间中最小的,也应该移除,因为这个区间的其他数 因此输入:5 [5,10,6,7,8] 输出:4 注:可以去掉 10,形成数组 [5, 6,7, 8],长度为3。
版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。