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

這題的題目在這裡:

題目敘述

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

測試範例

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