算法筆試模拟題精解之“連綿的群山”

線上程式設計介紹

阿裡雲開發者社群線上程式設計産品，針對廣大開發者學習、實踐、面試、應聘、考試認證等打造的免費線上刷題神器。題庫來自筆試模拟題、算法大賽模拟題等，界面整潔明了，操作簡單，為使用者營造專心答題的學習環境。點選連結開始體驗：

https://developer.aliyun.com/coding

本文為大家介紹其中的 第79題：連綿的群山 的題目解析，具體如下：

題目描述

等級：中等

知識點：DP

檢視題目：連綿的群山

小森家的北面有一條連綿的山脈，山脈高低起伏。小森很好奇這些山中最多有幾座連續的山頭是越來越高的，當然這對小森來說太簡單了。

他又想，假如可以移除其中一座，這個答案最大又會是多少？當然了，他也可以選擇不移除任何一座山峰。1 <= n <= 100000, 1 <= a[i] <= 1000000000。

輸入内容為兩行，第一行為山峰的數量n，第二行為n個數字，表示每個山頭的高度。

輸出一個數字，表示最大值。

示例1

輸入：

5

[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);
 }           

看完之後是不是有了想法了呢，快來練練手吧>>