算法笔试模拟题精解之“连绵的群山”

算法笔试模拟题精解之“连绵的群山”

贡献者 | 张鹏飞

简介：可以将山化分为几个小连续区间，每个区间保证越来越高，并且保证每个

区间尽可能的长。除第一个和最后一个区间，中间的其余区间，有移除可能的是每个

区间的最小值和最大值，第一个区间有移除可能的是最小值，最后一个区间有移除可

能的是最大值。这样才能找出最长的山的区间。

题目描述

等级：中等

知识点：DP

查看题目：连绵的群山

小森家的北面有一条连绵的山脉，山脉高低起伏。小森很好奇这些山中最多有几

座连续的山头是越来越高的，当然这对小森来说太简单了。

他又想，假如可以移除其中一座，这个答案最大又会是多少？当然了，他也可以

选择不移除任何一座山峰。1 <= n <= 100000, 1 <= a[i] <= 1000000000。

输入内容为两行，第一行为山峰的数量 n，第二行为 n 个数字，表示每个山头的

高度。

输出一个数字，表示最大值。

示例 1

输入：

[5,10,6,7,8]

输出：

4

注意

可以去掉 10，形成数组 [5, 6, 7, 8]，长度为 3。

解题思路：

大致思路：可以将山化分为几个小连续区间，每个区间保证越来越高，并且保证

每个区间尽可能的长。除第一个和最后一个区间，中间的其余区间，有移除可能的是

每个区间的最小值和最大值，第一个区间有移除可能的是最小值，最后一个区间有移

除可能的是最大值。这样才能找出最长的山的区间。

具体过程：初始化两个数组，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 前面那座山，也就是上一个区间最高的山

if(a[oneIndex[i]-2]<=a[oneIndex[i]])

ans=Math.max(arr[oneIndex[i+1]-1]+arr[oneIndex[i]-2],ans);

Else ans=Math.max(arr[oneIndex[i]-1],ans);

再移除 1 这座山，也就是当前区间最低的山 ( 有同学可以不明白为什么最低的山

也有移除的可能性 , 看看下面的例子 )

可能出现这种情况

2，4，5，6，3，8，9，11，13，15

这样的话，即使 3 是第二个区间中最小的，也应该移除，因为这个区间的其他数

字都很大，而且可以和前面的区间对接上。

if(oneIndex[i]+1<n) { if(a[oneIndex[i]-1]<=a[oneIndex[i]+1])

ans=Math.max(arr[oneIndex[i+1]-1]+arr[oneIndex[i]-1]-1,ans);

Else ans=Math.max(arr[oneIndex[i]-1],ans);

}

看完之后是不是有了想法了呢，快来练练手吧 >> 查看题目：连绵的群山