开发者社区> 问答> 正文

遇到一个求山的区间的问题,求解答。

小森家的北面有一条连绵的山脉,山脉高低起伏。小森很好奇这些山中最多有几座连续的山头是越来越高的,当然这对小森来说太简单了。他又想,假如可以移除其中一座,这个答案最大又会是多少?当然了,他也可以选择不移除任何一座山峰。1<=n<=100000, 1<=a[i] <=1000000000。输入内容为两行,第一行为山峰的数量n,第二行为n个数字,表示每个山头的高度。输出一个数字,表示最大值。

展开
收起
游客4skzfvnrxrzbi 2021-12-23 16:43:47 455 0
1 条回答
写回答
取消 提交回答
  • 初始化两个数组,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 前面那座山,也就是上一个区间最高的山。image.png 再移除 1 这座山,也就是当前区间最低的山 ( 有同学可以不明白为什么最低的山 也有移除的可能性 , 看看下面的例子 ) image.png

    可能出现这种情况image.png

    这样的话,即使 3 是第二个区间中最小的,也应该移除,因为这个区间的其他数image.png 因此输入:5 [5,10,6,7,8] 输出:4 注:可以去掉 10,形成数组 [5, 6,7, 8],长度为3。

    2021-12-23 18:34:48
    赞同 展开评论 打赏
问答分类:
问答地址:
问答排行榜
最热
最新

相关电子书

更多
低代码开发师(初级)实战教程 立即下载
冬季实战营第三期:MySQL数据库进阶实战 立即下载
阿里巴巴DevOps 最佳实践手册 立即下载