Day 08 : Longest Mountain in Array

先来看简述题目的定义

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