2022-04-22|閱讀時間 ‧ 約 6 分鐘

【LeetCode】896. Monotonic Array || 這一刻,意識到了自己的成長。

Input: nums = [1,2,2,3] Output: true
Input: nums = [6,5,4,4] Output: true
Input: nums = [1,3,2] Output: false

題目: 給一個陣列,判斷內容是不是遞增或遞減

第一版

class Solution {
    public boolean isMonotonic(int[] nums) {
      boolean isIncrease = true;
      boolean isDecrease = true;
    for (int i = 0; i < nums.length - 1; i++) {
      if (nums[i] < nums[i+1]) {
        isDecrease = false;
        continue;
      }
      if (nums[i] > nums[i+1]) {
        isIncrease = false;
        continue;  
      }
    }
    return isIncrease || isDecrease;
  }
}
初始兩個boolean flag,在迴圈過程中判斷遞增、遞減性是否還是維持,否則就提前進入下一輪,其中如果是相等的情況並不影響結果,因此不用特別處理。
在通過測資的結果下,試著進行重構跟優化。flag一旦被改成false,其實也沒有繼續在迴圈中進行判斷的必要,因此試著把for迴全拆成兩個,各自對兩個flag進行判斷,改成以下版本。

第二版

class Solution {
  public boolean isMonotonic(int[] nums) {
    if (nums.length <= 1) {
      return true;
    }
    boolean isIncrease = true;
    boolean isDecrease = true;

    for (int i = 0; i < nums.length - 1; i++) {
      if (nums[i] < nums[i+1] && isDecrease) {
        isDecrease = false;
        break;
      }
    }
    for (int i = 0; i < nums.length - 1; i++) {
       if (nums[i] > nums[i+1] && isIncrease) {
        isIncrease = false;
        break;
       }
    }
    return isIncrease || isDecrease;
  }
}
程式碼多了重複的迴圈,但實際上針對flag一改變就可以提前結束迴圈,不會受制於另一個flag的判斷,反而速度上可以提升。另外,當測資陣列內只有一個數字,也沒有判斷的必要,可以提前回傳。
執行結果與第一版的記憶體使用同樣都是92MB上下,執行速度卻從5ms左右降到只需要2ms

第三版

class Solution {
  public boolean isMonotonic(int[] nums) {
    if (nums.length <= 1) {
      return true;
    }
    return isIncrease(nums) || isDecrease(nums);
  }

  private boolean isIncrease(int[] nums) {
    for (int i = 0; i < nums.length - 1; i++) {
      if (nums[i] > nums[i+1] ) {
        return false;
      }
    }
    return true;
  }

  private boolean isDecrease(int[] nums) {
    for (int i = 0; i < nums.length - 1; i++) {
      if (nums[i] < nums[i+1]) {
        return false;
      }
    }
    return true;
  }
}
最後,把判斷跟迴圈另外抽出來成method,原本主要的isMonotonic method也變得很直觀: 是遞增或者是遞減,就符合條件結果。
由於過程中也沒有另外建立變數,僅將輸入的陣列傳遞出去得到判斷,不會有其他的資源配置耗費。
執行結果1 ms ,記憶體用量52.3MB
執行結果1 ms ,記憶體用量52.3MB

寫完之後

完成後本想看看討論區有沒有其他獨特的解法,突然發現這題官方有開放解答可以參考,發現第一個提供的解答跟我最終的版本差不多,只是我多處理了單一數字的特例。
  1. 從最初開始接觸程式,根本看不懂FORTRAN compiler吐給我的訊息
  2. 第一次刷Leetcode,光第一題就卡了大半天
  3. 慢慢可以寫出一版解答
  4. 解答後可以優化成更好的程式架構
這一刻,意識到了自己的成長。
分享至
成為作者繼續創作的動力吧!
© 2024 vocus All rights reserved.