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

2022/04/22閱讀時間約 5 分鐘

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

寫完之後

完成後本想看看討論區有沒有其他獨特的解法，突然發現這題官方有開放解答可以參考，發現第一個提供的解答跟我最終的版本差不多，只是我多處理了單一數字的特例。

從最初開始接觸程式，根本看不懂FORTRAN compiler吐給我的訊息
第一次刷Leetcode，光第一題就卡了大半天
慢慢可以寫出一版解答
解答後可以優化成更好的程式架構

這一刻，意識到了自己的成長。

12會員

62內容數

遇到的坑、解過的題、新知識的探索、舊時代的遺毒!? 工作後我發現，文件更新往往跟不上新需求的更迭，犯錯的歷史總是不斷重演。因此，我改變了方式，蒐集從程式上、系統上的每一次異常處理過程，好讓再次遇到相同的問題時能快速應變。此專題就是我的錯題本，期待日後不管在工作上或交流上遇到難題，都能輕鬆地應答：有什麼難的，我都踩過。

留言0

查看全部

發表第一個留言支持創作者！

Err500 的其他內容