2023-09-29|閱讀時間 ‧ 約 3 分鐘

陣列入門題 使否為單調數列 Monotonic Array Leetcode #896

raw-image

這題的題目在這裡:

題目敘述

題目會給一個輸入陣列,要求我們判斷所有的數字是否構成一組單調數列

也就是全部的數字構成一條單調遞增數列(逐漸變大)
或者一條單調遞減數列(逐漸變小)?


測試範例

Example 1:

Input: nums = [1,2,2,3]
Output: true

Example 2:

Input: nums = [6,5,4,4]
Output: true

Example 3:

Input: nums = [1,3,2]
Output: false

 


約束條件

Constraints:

  • 1 <= nums.length <= 105
  • -105 <= nums[i] <= 105

演算法

這題依照定義出發即可。

從左到右逐項檢查,如果發現遞增的某兩項,就把遞增的flag設成True。
同樣道理,如果發現遞減的某兩項,就把遞減的flag設成True。

只要發現 遞增 或 遞減 同時為True,代表無法構成一條單調數列返回False

反之,代表可以,返回True



程式碼

class Solution:
 def isMonotonic(self, nums: List[int]) -> bool:
  n = len(nums)
  
  increasing = False
  decreasing = False

  for i in range(n-1):

   if nums[i] < nums[i+1]:
    increasing = True
   
   elif nums[i] > nums[i+1]:
    decreasing = True
   
   # Both increasing and decreasing exist, it is not monotonic series
   if increasing and decreasing:
    return False

  return True



複雜度分析

時間複雜度:

O( n ) 從左到右掃描一遍,每個數字拿去和後面的數字比大小。

空間複查度:

O( 1 ) 只有用到固定大小的臨時變數,占用的記憶體空間為常數級別O(1)。


Reference:

[1] Python O( n ) sol. based on generator expression. 80%+ [ With explanation ] - Monotonic Array - LeetCode

分享至
成為作者繼續創作的動力吧!
© 2024 vocus All rights reserved.