先來看簡述題目的定義

1. 至少要有連續3個以上的整數
2. 從左往右看他要是嚴格遞增直到這些數中的最大值(山頂)，而後嚴格遞減

看完以上兩點，理所當然可以推論山頂不會在陣列的第一個數和最後一個數

Input: arr = [2,1,4,7,3,2,5]

以這個例子來說

這裡的山就是 [ 1, 4, 7, 3, 2]

符合

1. 陣列長度 > 3，其中 7 就是山頂

2. 1 < 4 < 7 和 7 > 3 > 2

應該大多數人看到題目的想法都是：
開始由左往右檢查，數字是否有嚴格遞增或是嚴格遞減的情況，並且追蹤目前最高的數值，以及目前山最長的長度，然後就開始嘗試實作程式碼，越寫越覺得有些地方沒有注意到，或是遇到一些情況時要額外處理，實作上變得很複雜。

今天想在這裡分享一個看起來不錯的解決方式。
既然我們要找出最長的山，我們應該要先知道所有的山頂在哪邊才能去比較對吧？
那我們就先把問題拆成
Step1. 找到所有的小山頂
而我們要判斷是否為小山頂
其實就是不斷判斷兩兩相鄰的數是否由持續遞增轉成持續遞減

Step2. 找出最長的山

因為我們已經知道山頂不會在頭尾，所以我們要比較的數可以從第二個位置到陣列的倒數第二個位置
我們來隨便用個例子來走訪，這個例子的結果應該會是6，山形為 [ 0, 10, 7, 6, -1, -3]

arr = [1, 2, 4, 4, 5, 0, 10, 7, 6, -1, -3, 3, 4]

我們開始拿arr[1]=2和他前後的數做比較：
因為2 > 1，但 2!>4，所以2不是山頂，但我們不能確定他是否在要到山頂的路
略過中間重複的敘述，接著我們走到5，發現4 < 5，且５> 4，所以5是我們現在找到的第一個山頂

接著我們找到10為第二個山頂，最後結束所有的查詢，在這個過程中我們需要Ｏ(N)來完成

再來看我們要做的第二個問題，也就是找出最長的山。
我們可以把剛剛找出來的山頂，也就是5和10分別檢查它的左邊不斷嚴格遞減的長度，同理右邊也是找不斷嚴格遞減的長度。
第二步驟的時間複雜度，如果我們在第一個步驟完全沒有找到山頂，則這一步只用花Ｏ(1)，因為不需要做任何事。但如果有的話，則需要Ｏ(N)。

不過，在下結論之前，我們先來想一件事。

我們是否一定得要把這兩個步驟順序完全拆開，用另一個空間來暫存我們找到的所有山頂？(如果最糟會需要Ｏ(N))

我們應該可以在找山頂的過程中，在找到的時後就開始頂執行第二個步驟，最後只需要額外儲存一個目前最大的長度即可，此外因為頂後面的部分應該是要嚴格遞減(下坡)，所以不可能會是下一個山頂的上坡，那我們根本就可以跳過下坡的這些數直接開始找下一個山頂不是嗎？
以這種方式，整體的時間複雜度Ｏ(N)，空間複雜度為Ｏ(1)

我們來實作吧！

var longestMountain = function (arr) {
  let longestLength = 0;
  let i = 1;
  while (i < arr.length - 1) {
    const isPeak = arr[i - 1] < arr[i] && arr[i + 1] < arr[i];
    if (!isPeak) {
      i++;
      continue;
    }

    let left = i - 2;
    while (left >= 0 && arr[left] < arr[left + 1]) {
      left--;
    }
    let right = i + 2;
    while (right < arr.length && arr[right] < arr[right - 1]) {
      right++;
    }

    const peakLength = right - left - 1;
    longestLength = Math.max(longestLength, peakLength);
    i = right;
  }
  return longestLength;
};

很多時候在想問題的時後會想把問題拆解，不過拆解完後也可以再思考看看，其實有些事情可以一氣喝成！

明日題目預告： Valid Palindrome