推 wwndbk: 大師 11/15 17:24
※ 編輯: ZooseWu (114.32.229.33 臺灣), 11/15/2023 17:24:24
1846. Maximum Element After Decreasing and Rearranging
給你一個正整數陣列arr，你可以執行下面兩個操作無數次：
1.減少：將某個元素的值變成一個更小的正整數
2.重新排序：將元素重新排序
操作完畢的陣列要符合下列條件：
1.首項為1 (arr[0] == 1)
2.任兩項之間最大差為1 (abs(arr[i] - arr[i-1]) <= 1)
回傳此時陣列中元素的最大值。
範例：
Input: arr = [2,2,1,2,1]
Output: 2
我們可以透過操作將陣列變成這樣：[1,2,2,2,1]
Input: arr = [100,1,1000]
Output: 3
先交換: [1, 100, 1000]
減少2: [1, 2, 1000]
減少3: [1, 2, 3]
Input: arr = [1,2,3,4,5]
Output: 5
原本就符合條件
Intuition:
排序之後計算答案。
Approach:
從題目讓我們可以做的兩個操作看下來
我們可以知道一個長度為n的陣列
它的最大值一定是嚴格單調遞增
陣列會長這樣[1, 2, 3 ... , n]
那不是最大值的情況是怎樣？
就是單調遞增
在遞增之後有重複的情況
例如[1, 2, 3, 4, 4]或是[1, 2, 4, 4, 4]
後面的陣列可以透過操作變成前面的陣列
所以我們只要不斷看數字有沒有遞增就好
如果遇到沒有遞增的情況就停頓
TS Code:
function maximumElementAfterDecrementingAndRearranging (arr: number[]):
number {
arr.sort((a, b) => (a - b))
let answer = 0
for (let i = 0; i < arr.length; i++) {
if (arr[i] > answer) answer++
}
return answer
}
--
Zoosewu
Yoututbe顯示PTT推文
可以在各個網站追實況或Live時使用
預覽圖: https://i.imgur.com/ZhtXdAJ.png https://i.imgur.com/WqbLNV3.png
完整介紹: https://github.com/zoosewu/PTTChatOnYoutube/tree/master/homepage
支援的網站: Youtube Twitch Holotools Niji-mado Holodex
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.32.229.33 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1700040217.A.59E.html