[演算法題目] Longest Peak

本題資訊

難度：easy
使用語言：C++
相關概念：Arrays

題目敘述

You may recall that an array arr is a mountain array if and only if:

• arr.length >= 3
• There exists some index i (0-indexed) with 0 < i < arr.length - 1 such that:
  • arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
  • arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Given an integer array arr, return the length of the longest subarray, which is a mountain. Return 0 if there is no mountain subarray.

我們必須在陣列中找到長度最長的一座山，並回傳這座山的長度。山的定義如上，其中要注意的是 peak 的部分，也就是說必須要有山峰，不接受台地地形XD

Idea

既然有點像是判斷地形，我想從頭沿著走應該可以？主要步驟如下：

• 如果第一步就開始下降，out!
• 上升，不停上升，盡可能地往上爬，長度增加
• 如果過程中遇到和前一個相等的數字（台地），out!
• 下降，不停下降，盡可能地下降，長度增加，直到條件不符合

大約是照著上面想法下去寫。count 計算目前正在走的長度，result 儲存目前遇到最大的長度，i 是目前所到位置的 index，所以每次執行也必須記得加一。

using namespace std;

int longestPeak(vector<int> array) {
  int n = array.size();
  int result = 0;
  int i = 1;

  while (i < n){
    int count = 1;
    if (array[i - 1] >= array[i]){
      i++;
      continue;
    }
    while (array[i - 1] < array[i] && i < n){
      count++;    
      i++;
    }
    if (array[i - 1] == array[i] || i >= n)
      continue;
    
    while (array[i - 1] > array[i] && i < n){
      count++;
      i++;
    }
    result = max(result, count);
  }
  return result;
}

時間複雜度：\(O(n)\)，\(n\) 是指陣列元素個數。
空間複雜度：\(O(1)\)