欣迪

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

var validMountainArray = function(arr) {
    if (arr.length < 3) return false
    let onTop = false
    for (let i = 0; i < arr.length - 1; i++) {
        if (arr[i] === arr[i+1]) {
            return false
        }
        
        if (i > 0 && arr[i] > arr[i+1]) {
            onTop = true
        }
        
        if (!onTop && arr[i] >= arr[i+1]) {
            return false
        }
        
        if (onTop && arr[i] <= arr[i+1]) {
            return false
        }
             
    }
    return true && onTop
};

基礎, 但是有趣。

常常覺得,寫程式就像交代一個工人做事。

這個工人很酷,絕對會按照你交代的事情去完成,不會去糾正你,也不怎麼會變通。但是絕對按照你的吩咐。

所以在解決問題時,我會先用自己聽得懂的語言對自己說一次,或是寫在紙上。這個很適合示範一下。

以這題為例,該怎麼判斷是不是山形的陣列:

1. 檢查每個數字吧: 寫了第一個迴圈

var validMountainArray = function(arr) {
   
    for (let i = 0; i < arr.length - 1; i++) {
      
    }
};

2. 如果陣列的內容只有兩個,不可能是山形。

var validMountainArray = function(arr) {
   
  	// 陣列長度不可以小於 3
    if (arr.length < 3) return false
  
  	for (let i = 0; i < arr.length - 1; i++) {
      
    }
};

3. 如果連續出現兩個一樣的數字,也可以排除。

var validMountainArray = function(arr) {
   
    if (arr.length < 3) return false
  
  	for (let i = 0; i < arr.length - 1; i++) {
      // 續出現兩個一樣的數字,排除
      if (arr[i] === arr[i+1]) {
            return false
      }
      
    }
};

4. 接下來的判斷要分成兩個部分,登上山頂前,和登上山頂後。 做一個參數來記錄是不是登上山頂了。

var validMountainArray = function(arr) {
   
    if (arr.length < 3) return false
    
  // 做一個參數來記錄是不是登上山頂了
  	let onTop = false
  	for (let i = 0; i < arr.length - 1; i++) {
      if (arr[i] === arr[i+1]) {
            return false
      }    
    }
};

5. 怎麼樣算登上山頂呢? 不是第一個數字而且開始下坡

var validMountainArray = function(arr) {
   
    if (arr.length < 3) return false
    
  	let onTop = false
  	for (let i = 0; i < arr.length - 1; i++) {
      if (arr[i] === arr[i+1]) {
            return false
      }
      
      // 不能是第一個數字 i > 0
      // 下一個數字開始下降 arr[i] > arr[i+1]
      if (i > 0 && arr[i] > arr[i+1]) {
            onTop = true
      }
      
    }
};

6. 登上山頂前,數字要一直上升,登上山頂後數字要一直下降。 通過這些檢核就算合格。

var validMountainArray = function(arr) {
   
    if (arr.length < 3) return false
    
  	let onTop = false
  	for (let i = 0; i < arr.length - 1; i++) {
      if (arr[i] === arr[i+1]) {
            return false
      }
      
      if (i > 0 && arr[i] > arr[i+1]) {
            onTop = true
      }
      
      // 登頂前,數字要一直上升
	  if (!onTop && arr[i] >= arr[i+1]) {
            return false
      }
      // 登頂後,數字要一直下降
      if (onTop && arr[i] <= arr[i+1]) {
            return false
      }
      
    }
    
	// 通過這些檢核就算合格
  	return true
};

7. 檢視一下是否少了什麼。 沒錯,如果陣列是 [1, 2, 3, 4],可以閃過我們的檢核,因為他一直保持 onTop 在 false 的狀態,也一直處於數字上升。 因此,必須在最後增加一個條件,必須要完成登頂的動作。

var validMountainArray = function(arr) {
   
    if (arr.length < 3) return false
    
  	let onTop = false
  	for (let i = 0; i < arr.length - 1; i++) {
      if (arr[i] === arr[i+1]) {
            return false
      }
      
      if (i > 0 && arr[i] > arr[i+1]) {
            onTop = true
      }
      
	  if (!onTop && arr[i] >= arr[i+1]) {
            return false
      }
      
      if (onTop && arr[i] <= arr[i+1]) {
            return false
      }
      
    }
  	// 必須要完成過登頂這件事
  	return onTop && true
};

呼,總算大功告成。 先用自己的話交代一遍,總是能很快的寫出解決的雛形,接下來就是內建函式的熟練度和經驗。

透過不斷解題的過程中,慢慢的也會改變自己看待事物的看法,解決日常生活事件的方式。

訂閱 IT-Monk

訂閱最新文章的發布消息! 😚😚😚
Loading

作者介紹 - 欣迪

欣迪

從設計到寫程式,發現自己有追求前端技巧的自虐傾向。不斷的踩坑,再從坑裡爬出來,慢慢對攀岩有點心得。 目前在多間公司擔任網站設計顧問。 同時也是網站架設公司負責人。

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。