0941. Valid Mountain Array (Easy)

寫在前面

2022/03/09: 配合官方修改格式，各項優惠連結3/14之後會失效，
這邊更新新版的連結給大家~**

從 LeetCode 學演算法｜完整解題技巧 + 面試成功指南： https://bit.ly/lc2022all

容筆者工商一下，
「從Leetcode學演算法｜進階篇」 這次選了40道難度加深的LeetCode題目，
同樣也會細部解說對應的技巧及須要掌握的演算法！
同時這次購買進階篇的話，
額外還加贈**「從Leetcode學演算法｜面試篇」** ！
當中包含了面試準備須知分享 ，及訪談國內外不同經驗的工程師 ，
讓你不論是想走前端/後端/一般軟工 或者是想找國外的工作 ，
是初學想轉職 還是正在工作 ，都能夠從中得到收穫呦！
有興趣的朋友可以使用下面的優惠～
「從Leetcode學演算法｜進階篇」+「從Leetcode學演算法｜面試篇」 ：
https://bit.ly/lc2022adv

Question

Given an array of integers arr, return true if and only if it is a valid mountain array.

Recall that arr is a mountain array if and only if:

• arr.length >= 3
• There exists some i 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]

Example 1

1
2

Input: arr = [2,1]
Output: false

Example 2

1
2

Input: arr = [3,5,5]
Output: false

Example 3

1
2

Input: arr = [0,3,2,1]
Output: true

Constraints

• 1 <= arr.length <= 104
• 0 <= arr[i] <= 104

分析/解題

給定一個整數陣列arr，若且唯若它是一個合格的mountain array時，
回傳true(否則回傳false)。
mountain array的條件要符合以下幾點:

1. arr長≥3
2. 存在i，0<i<arr.length-1使得:
   arr[0] < arr[1] < … < arr[i-1] < arr[i] 且
   arr[i] > arr[i + 1] > … > arr[arr.length-1]

為了避免大家隔太久沒有練習(我也是)，而且快過年了不要讓大家太燒腦，
今天我們就介紹簡單一點的題目就好XD！

在LeetCode的題型中，有一些簡單的題目的規格，
會呈現為只要題目讀得懂，按要求做完就會答對的形式，
本題就是相當明確的例子之一。

我們來看看要求：mountain array
前面必須要嚴格遞增 ，後面必須要嚴格遞減 ，
中間的arr[i]值為整個陣列的最高點。
同時限制了長度必須大於等於3，也就是上下坡都必然存在。

那麼解題方式就很明確了：

1. 先檢查長度是否≥3，且arr[0]是否小於arr[1]
   (一定要檢查，因為我們希望上下坡都存在 )
2. 從陣列的開頭開始以i計數，往後沿途比較arr[i]跟arr[i+1]，
   一路遞增到遞減轉折出現為止(也就是第一個arr[i] >arr[i+1])
3. 在2當中如果出現前後相等 的狀況可直接回傳False，
   同時，如果還沒下坡就已經走到底(i + 1 == arr.length) 的話，
   也要回傳False 。
4. 沿路下坡，一路走到尾端
5. 如果沿途均符合的話(會走到i + 1 == arr.length )，則回傳true；
   如果沿途變平或上坡的話，需在4的位置提早停下，
   這樣子就可以藉由是否走到尾端這點來判斷要回傳true或false。

依此，寫成程式碼如下。

Java

可以看到我們在上坡的時候使用迴圈，
每次檢查就做兩件事來確認是否離開迴圈：

1. 是不是走到底了 -> 走到底的話就不對了，因為還沒下坡
2. 是不是有在走上坡 -> 變平的話不對，只有變下坡可以接受

而下坡時只有一路下坡走到底可以被接受。

Python

Python寫法基本上一致，所以說這題不難，對吧XD！
關鍵還是在於是否能確切釐清題目要求，
例如如果沒有寫A[0] ≥ A[1]的檢查的話，
就有可能碰到只有下坡的陣列，從而讓檢查結果出問題喲！

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(N)/O(1)，這題最多需要掃完整個陣列，
且我們只有多使用一個i的變數。)

相似及延伸

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~

想看看其他題目嗎？
歡迎從第零篇 找你想要的！

同時追蹤粉專以獲得更多新文章的通知：
跟著Desolve學程式

另外，「從Leetcode學演算法｜基礎篇」 已經回原價囉，
先前的優惠碼會失效，但這邊仍然為讀者保留了300塊的折抵，
雖然整捆一起買總體比較划算 (差290而已就有整組了阿XD)，
如果你還是想先試試基礎課的話，
300元折抵的連結 在這邊：
https://bit.ly/lc2022base