找出數組中的峰值

給你一個下標從 0 開始的數組 mountain 。你的任務是找出數組 mountain 中的所有 峰值。

以數組形式返回給定數組中 峰值 的下標，順序不限 。

注意

• 峰值 是指一個嚴格大于其相鄰元素的元素。
• 數組的第一個和最后一個元素 不 是峰值。

示例 1

輸入：mountain = [2,4,4]
輸出：[]
解釋：mountain[0] 和 mountain[2] 不可能是峰值，因為它們是數組的第一個和最后一個元素。mountain[1] 也不可能是峰值，因為它不嚴格大于 mountain[2]。因此，答案為 []。

示例 2

輸入：mountain = [1,4,3,8,5]
輸出：[1,3]
解釋：mountain[0] 和 mountain[4] 不可能是峰值，因為它們是數組的第一個和最后一個元素。mountain[2] 也不可能是峰值，因為它不嚴格大于 mountain[3] 和 mountain[1]。但是 mountain[1] 和 mountain[3] 嚴格大于它們的相鄰元素。因此，答案是 [1,3]。

提示

• 3 <= mountain.length <= 100
• 1 <= mountain[i] <= 100

代碼

int* findPeaks(int* mountain, int mountainSize, int* returnSize) {int* res = (int*)malloc(sizeof(int) * (mountainSize - 2));*returnSize = 0;for (int i = 1; i < mountainSize - 1; i++){if(mountain[i] > mountain[i-1] && mountain[i] > mountain[i+1]){res[(*returnSize)] = i;(*returnSize)++;}}return res;
}

代碼分析

1. 函數參數：

   • int* mountain: 指向表示山脈的數組的指針。
   • int mountainSize: 數組的大小。
   • int* returnSize: 返回結果數組的大小。

2. 變量初始化：

   • int* res = (int*)malloc(sizeof(int) * (mountainSize - 2)): 為存儲峰值下標的結果數組分配內存。結果數組的大小不會超過 mountainSize - 2。
   • *returnSize = 0: 初始化返回結果數組的大小為 0。

3. 遍歷數組：

   • for (int i = 1; i < mountainSize - 1; i++): 從數組的第二個元素遍歷到倒數第二個元素。

4. 檢查峰值條件：

   • if(mountain[i] > mountain[i-1] && mountain[i] > mountain[i+1]): 如果當前元素嚴格大于其相鄰元素，則將其下標存入結果數組，并增加返回結果數組的大小。

5. 返回結果：

   • return res: 返回存儲峰值下標的結果數組。

復雜度分析

• 時間復雜度：O(n)

  • 該算法僅需遍歷一次數組，因此時間復雜度為 O(n)，其中 n 是數組 mountain 的長度。

• 空間復雜度：O(n)

  • 該算法使用了一個額外的數組來存儲峰值下標，因此空間復雜度為 O(n)，其中 n 是數組 mountain 的長度。

結果