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

閱讀時間約 2 分鐘
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

raw-image



程式碼

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

59會員
347內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言0
查看全部
發表第一個留言支持創作者!
你可能也想看
川普當選,對台股是利多還是利空?川普在槍擊事件中所表現出來的英勇形象,讓他贏得美國總統大選幾乎已成定局。沒想到他隨口的一句話「台灣搶走美國的晶片生意,所以要付保護費」,就讓台積電在短短三天跌掉超過100 元,台股也跌掉1100點以上。台積電、台股會就此一路下跌嗎?未來該如何因應?  
Thumbnail
2024-07-20
61
金融科技與生活美學的融合 CUBE App實踐自我理想最近開啟了研究工作,也開始斜槓著手團購、行銷、洽談業務,慢慢想打造一條屬於自己的道路,而工作忙碌之虞,總忘記自己刷卡消費明細、信用卡繳費,還會忽略了最應該的投資理財,也常常在忙碌奔波中忘記信用卡優惠,國泰世華CUBE App給足了這些功能和服務。 日常生活與數位、科技形影不離,同時也拉近彼此距
Thumbnail
2024-07-11
13
陣列:Go語言中的數據小倉庫👨‍💻簡介 陣列就像是一個儲存相同類型資料的容器,你可以想像成裝滿了一樣東西的盒子,每個東西都叫做陣列元素。這種類型可以是基本的,像是整數或字串,也可以是你自己定義的型別。不過陣列有個限制,就是大小一旦確定就無法改變。在Go語言裡,陣列的長度也是型別的一部分。
Thumbnail
2023-08-24
2
震巽为一炁先天八卦,「震巽为一炁[qì]」,震一阳生,巽一阴生,故为「一炁」。希伯来字母第一个字母alef:א。 意思是善恶分开,事情的开始。上帝是第一推动,上帝创造善的同时,对称的创造了恶。律法区分善恶,意味着善恶是对称的,善恶都是上帝创造的,都是从上帝而来的。上主是一,善恶是上主的两种力量,诫命是让选民去
Thumbnail
2023-07-15
1
震為雷震為雷 上下皆震卦,表示接二連三的打雷 打雷就會怕怕,但克服怕怕的恐懼便是不驚慌失措 這是我第四個我每日卦裡抽到的純卦 所謂的純卦就是上下皆是八卦的同一卦 比如我已經抽過的 乾為天 就是上下都是乾卦所以你會看到6橫一, 艮為山就是上下都是艮卦,離為火就是上下都是離卦 當然因為我是抽每日的,所以算是一
Thumbnail
2023-05-14
0
「鎮館之寶」開缺!荷蘭莫瑞泰斯皇家美術館徵求創意替代品莫瑞泰斯皇家美術館積極邀請大家「交出你的珍珠耳環少女!」,提供自己受到《戴著珍珠耳環的少女》啟發的作品,任何形式、任何媒材,通通都可以!
Thumbnail
震盪格局轉為空頭走勢,擁抱現金等待落底。  今日加權指數帶量下殺 263 點,全都在意料之中,原先預期為結算日殺盤,沒想到紅太陽突然宣布賣美債影響全球股市下挫。注意看到今日的下殺是有帶量的,而且也就是今日的殺盤中仍然帶有部分買盤,否則這個交易量不會僅 3 家跌停。當然這樣的買盤並不會結束跌勢,而這只是起始點,直到真正的恐慌出現並伴隨著大量
Thumbnail
2022-12-20
4
震驚全球的奧斯卡send tree pay事件背後,其實有許多值得我們思考的議題!隨著奧斯卡的落幕, 這一巴掌響出天際成為熱門題材, 成為大家爭相討論模仿的話題, 但其實這背後也帶出許多的議題討論 2022年第94屆奧斯卡頒獎典禮上,喜劇演員—克里斯洛克(Chris Rock) 在舞台上大開威爾史密斯(Will Smith)的妻子 便衝上台給了克里斯一個響亮的巴掌,
Thumbnail
2022-04-02
2
振興五倍券/綁數位券?還是領紙本券? 平日都睡很晚的我,今天早上為了搶前四百萬名數位綁定才有的好食券難得早起,不到九點就把讀卡機啥的準備好,連官網及銀行的連結都先連好,免得活動開始,連網頁都點不進去。
Thumbnail
2021-09-22
6
振興書店的初心者書單不知道你去預購振興券了嗎?經過此次疫情似乎也有不少人投向了書籍的懷抱,可能你就是其中之一。因此你想邁入書店購入幾本書,卻在茫忙書海中疑惑了嗎?這份書單能帶給你初次在書海中遨遊的方向!
Thumbnail
2020-07-05
8
川普當選,對台股是利多還是利空?川普在槍擊事件中所表現出來的英勇形象,讓他贏得美國總統大選幾乎已成定局。沒想到他隨口的一句話「台灣搶走美國的晶片生意,所以要付保護費」,就讓台積電在短短三天跌掉超過100 元,台股也跌掉1100點以上。台積電、台股會就此一路下跌嗎?未來該如何因應?  
Thumbnail
2024-07-20
61
金融科技與生活美學的融合 CUBE App實踐自我理想最近開啟了研究工作,也開始斜槓著手團購、行銷、洽談業務,慢慢想打造一條屬於自己的道路,而工作忙碌之虞,總忘記自己刷卡消費明細、信用卡繳費,還會忽略了最應該的投資理財,也常常在忙碌奔波中忘記信用卡優惠,國泰世華CUBE App給足了這些功能和服務。 日常生活與數位、科技形影不離,同時也拉近彼此距
Thumbnail
2024-07-11
13
陣列:Go語言中的數據小倉庫👨‍💻簡介 陣列就像是一個儲存相同類型資料的容器,你可以想像成裝滿了一樣東西的盒子,每個東西都叫做陣列元素。這種類型可以是基本的,像是整數或字串,也可以是你自己定義的型別。不過陣列有個限制,就是大小一旦確定就無法改變。在Go語言裡,陣列的長度也是型別的一部分。
Thumbnail
2023-08-24
2
震巽为一炁先天八卦,「震巽为一炁[qì]」,震一阳生,巽一阴生,故为「一炁」。希伯来字母第一个字母alef:א。 意思是善恶分开,事情的开始。上帝是第一推动,上帝创造善的同时,对称的创造了恶。律法区分善恶,意味着善恶是对称的,善恶都是上帝创造的,都是从上帝而来的。上主是一,善恶是上主的两种力量,诫命是让选民去
Thumbnail
2023-07-15
1
震為雷震為雷 上下皆震卦,表示接二連三的打雷 打雷就會怕怕,但克服怕怕的恐懼便是不驚慌失措 這是我第四個我每日卦裡抽到的純卦 所謂的純卦就是上下皆是八卦的同一卦 比如我已經抽過的 乾為天 就是上下都是乾卦所以你會看到6橫一, 艮為山就是上下都是艮卦,離為火就是上下都是離卦 當然因為我是抽每日的,所以算是一
Thumbnail
2023-05-14
0
「鎮館之寶」開缺!荷蘭莫瑞泰斯皇家美術館徵求創意替代品莫瑞泰斯皇家美術館積極邀請大家「交出你的珍珠耳環少女!」,提供自己受到《戴著珍珠耳環的少女》啟發的作品,任何形式、任何媒材,通通都可以!
Thumbnail
震盪格局轉為空頭走勢,擁抱現金等待落底。  今日加權指數帶量下殺 263 點,全都在意料之中,原先預期為結算日殺盤,沒想到紅太陽突然宣布賣美債影響全球股市下挫。注意看到今日的下殺是有帶量的,而且也就是今日的殺盤中仍然帶有部分買盤,否則這個交易量不會僅 3 家跌停。當然這樣的買盤並不會結束跌勢,而這只是起始點,直到真正的恐慌出現並伴隨著大量
Thumbnail
2022-12-20
4
震驚全球的奧斯卡send tree pay事件背後,其實有許多值得我們思考的議題!隨著奧斯卡的落幕, 這一巴掌響出天際成為熱門題材, 成為大家爭相討論模仿的話題, 但其實這背後也帶出許多的議題討論 2022年第94屆奧斯卡頒獎典禮上,喜劇演員—克里斯洛克(Chris Rock) 在舞台上大開威爾史密斯(Will Smith)的妻子 便衝上台給了克里斯一個響亮的巴掌,
Thumbnail
2022-04-02
2
振興五倍券/綁數位券?還是領紙本券? 平日都睡很晚的我,今天早上為了搶前四百萬名數位綁定才有的好食券難得早起,不到九點就把讀卡機啥的準備好,連官網及銀行的連結都先連好,免得活動開始,連網頁都點不進去。
Thumbnail
2021-09-22
6
振興書店的初心者書單不知道你去預購振興券了嗎?經過此次疫情似乎也有不少人投向了書籍的懷抱,可能你就是其中之一。因此你想邁入書店購入幾本書,卻在茫忙書海中疑惑了嗎?這份書單能帶給你初次在書海中遨遊的方向!
Thumbnail
2020-07-05
8