前往
大廳
主題

LeetCode - 941. Valid Mountain Array 解題心得

Not In My Back Yard | 2021-02-20 00:00:04 | 巴幣 0 | 人氣 389

題目連結:


題目意譯:
給定一整數陣列 arr,回傳真(True)若且唯若其為一個合法的山陣列。

複習一下,arr 為一山陣列若且唯若:
arr.length ≧ 3 、
存在某個 i ,其中 0 < i < arr.length - 1 ,使得:
arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > ... > arr[arr.length - 1]


限制:
1 ≦ arr.length ≦ 10 ^ 4
0 ≦ arr[i] ≦ 10 ^ 4



範例測資:
範例 1:
輸入: arr = [2,1]
輸出: false

範例 2:
輸入: arr = [3,5,5]
輸出: false

範例 3:
輸入: arr = [0,3,2,1]
輸出: true


解題思維:
利用這題的解法去找到一個 i 值(可能為山頂的數字之位置),找到了以後就檢查 arr[i] 是否真的為山頂:
先檢查 arr[0] < arr[1] < ... < arr[i - 1] < arr[i],
再檢查 arr[i] > arr[i + 1] > ... > arr[arr.length - 1],
兩個迴圈即可。

如果都符合則表示我們找到的山頂是真的山頂,所以陣列 arr 是一座山,因此回傳真;反之,arr 不是山,回傳假(False)。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作