Free AI web copilot to create summaries, insights and extended knowledge, download it at here

2313

Abstract

i</code> with <code>0 such that:</li><li><code>arr[0] < arr[1] < ... < arr[i - 1] < arr[i]</code></li><li><code>arr[i] > arr[i + 1] > ... > arr[arr.length - 1]</code></li></ul><figure id="00ed"><img src="https://cdn-images-1.readmedium.com/v2/resize:fit:800/0*_l8cBax99BYE7Ikv.png"><figcaption></figcaption></figure>Example 1:<div id="b916"><pre>Input: arr = [2,1] Output: false</pre></div>Example 2:<div id="edc7"><pre>Input: arr = [3,5,5] Output: false</pre></div>Example 3:<div id="b188"><pre>Input: arr = [0,3,2,1] Output: true</pre></div>Constraints:<ul><li><code>1 <= arr.length <= 104</code></li><li><code>0 <= arr[i] <= 104</code></li></ul>分析/解題： 給定一個整數陣列arr，若且唯若它是一個合格的mountain array時，回傳true(否則回傳false)。 mountain array的條件要符合以下幾點:

arr長≥3
存在i，0<i<arr.length-1使得: arr[0]="" <="" arr[1]="" …="" arr[i-1]="" arr[i]="" 且=""> arr[i + 1] > … > arr[arr.length-1]</i<arr.length-1使得:>為了避免大家隔太久沒有練習(我也是)，而且快過年了不要讓大家太燒腦，今天我們就介紹簡單一點的題目就好XD！在LeetCode的題型中，有一些簡單的題目的規格，會呈現為只要題目讀得懂，按要求做完就會答對的形式，本題就是相當明確的例子之一。我們來看看要求：mountain array 前面必須要嚴格遞增，後面必須要嚴格遞減，中間的arr[i]值為整個陣列的最高點。同時限制了長度必須大於等於3，也就是上下坡都必然存在。那麼解題方式就很明確了：
先檢查長度是否≥3，且arr[0]是否小於arr[1] (一定要檢查，因為我們希望上下坡都存在)
從陣列的開頭開始以i計數，往後沿途比較arr[i]跟arr[i+1]，一路遞增到遞減轉折出現為止(也就是第一個arr[i] >arr[i+1])
在

Options

2當中如果出現前後相等的狀況可直接回傳False，同時，如果還沒下坡就已經走到底(i + 1 == arr.length)的話，也要回傳False。 4. 沿路下坡，一路走到尾端 5. 如果沿途均符合的話(會走到i + 1 == arr.length)，則回傳true；如果沿途變平或上坡的話，需在4的位置提早停下，這樣子就可以藉由是否走到尾端這點來判斷要回傳true或false。依此，寫成程式碼如下。Java:可以看到我們在上坡的時候使用迴圈，每次檢查就做兩件事來確認是否離開迴圈：

是不是走到底了 -> 走到底的話就不對了，因為還沒下坡

是不是有在走上坡 -> 變平的話不對，只有變下坡可以接受而下坡時只有一路下坡走到底可以被接受。 <figure id="3f24"> <div> <div>

         <iframe class="gist-iframe" src="/gist/Desolve/2e0e87626e17ebc1f4729134c817fd7e.js" allowfullscreen="" frameborder="0" height="undefined" width="undefined">
       </div>
     </div>
 </figure></iframe></div></div></figure><p id="0314"><b>Python:</b></p><p id="6f52">Python寫法基本上一致，所以說這題不難，對吧XD！

關鍵還是在於是否能確切釐清題目要求，例如如果沒有寫A[0] ≥ A[1]的檢查的話，就有可能碰到只有下坡的陣列，從而讓檢查結果出問題喲！ <figure id="e8fc"> <div> <div>

            <iframe class="gist-iframe" src="/gist/Desolve/81650fdb8adc9337e9ebe7f963469467.js" allowfullscreen="" frameborder="0" height="undefined" width="undefined">
          </div>
        </div>
    </figure></iframe></div></div></figure><p id="5655"><b>面試實際可能會遇到的問題：

「時間/空間複雜度？」 (O(N)/O(1)，這題最多需要掃完整個陣列，且我們只有多使用一個i的變數。)相似及延伸： Special Thanks suggestions/corrections from viewers: (歡迎提供意見協助更正歐~)從LeetCode學演算法，我們下次見囉，掰~想看看其他題目嗎？歡迎從<a href="https://desolve.medium.com/%E5%BE%9Eleetcode%E5%AD%B8%E6%BC%94%E7%AE%97%E6%B3%95-0-6c121bd8b579?source=friends_link&sk=357a5430bc0a89c3b3db64b48101ab6d">第零篇</a>找你想要的！同時追蹤粉專以獲得更多新文章的通知： <a href="https://www.facebook.com/learnwithdesolve">跟著Desolve學程式</a>另外，「從Leetcode學演算法｜基礎篇」已經回原價囉，先前的優惠碼會失效，但這邊仍然為讀者保留了300塊的折抵，雖然整捆一起買總體比較划算(差290而已就有整組了阿XD)，如果你還是想先試試基礎課的話， 300元折抵的連結在這邊： <a href="https://bit.ly/lc2022base">https://bit.ly/lc2022base</a><div id="d3a5"><pre>如果你／妳覺得這篇文章不錯，請拍手並給5個Like。(點開SHOW EMBED!) 也請記得「Follow」我，隨時收看最新的文章。</pre></div></article></body>

從LeetCode學演算法 - 117 Array (17)

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

請幫我隨手點開下面的SHOW EMBED並按5個like～喜歡的話也可以幫我拍拍手～ (按讚不用錢，感謝支持寫作~)

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:

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

Example 2:

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

Example 3:

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 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

如果你／妳覺得這篇文章不錯，請拍手並給5個Like。(點開SHOW EMBED!)
也請記得「Follow」我，隨時收看最新的文章。