算法筆試模拟題精解之“非遞減序列”

線上程式設計介紹

阿裡雲開發者社群線上程式設計産品，針對廣大開發者學習、實踐、面試、應聘、考試認證等打造的免費線上刷題神器。題庫來自筆試模拟題、算法大賽模拟題等，界面整潔明了，操作簡單，為使用者營造專心答題的學習環境。點選連結開始體驗：

https://developer.aliyun.com/coding

本文為大家介紹其中的 第51題：非遞減序列 的題目解析，具體如下：

題目描述

題目等級：容易

知識點：數組

檢視題目：非遞減序列

給了n個數(1<=n<=100000)，分别為a1,a2,a3...an(1<=ai<=1000000000)，對于每一個ai，要麼不變，要麼讓它減1，問能否使這個序列變為非遞減序列，如果可以輸出"YES"，否則輸出"NO"。

輸入序列中數字的個數n，和n個數，表示每個ai的值

輸出一行字元串，如果可以變為非遞減序列輸出"YES"，否則輸出"NO"

示例1

輸入：

5

[1,1,2,1,5]

輸出：

"YES"

解題方法：

非遞減序列的定義為，序列中任意兩個相鄰的數，後一個數大于等于前面的數。

周遊數組，比較所有相鄰的數字，如果發現目前數字大于後一個的數字，則目前數字需要 -1，并做一個标記，表示這個數字已經減過1了，不能再減1了。同時如果一個數字減一之後，這個數字前面的數字如果比這個數字大了，前面太大的數字也需要跟着減一。

每次做-1操作時，都需要檢查标記，若發現在 -1 操作之前，數字已經做過标記，表明該數字無法再-1，序列無法變成非遞減序列，傳回NO。如果照上述操作整個數組都沒有問題，則表明序列可以變成非遞減序列，傳回YES。

時間複雜度：O(n^2)

空間複雜度：O(1)

看完之後是不是有了想法了呢，快來練練手吧>>