LeetCode 2779. Maximum Beauty of an Array After Applying Operation
周賽354。一開始又看錯題目,浪費一些時間。
最後用了次佳解,還挺擔心會不會TLE,好險沒有。
題目
輸入整數陣列nums和非負整數k。
每次操作,你可以:
- 從[0, nums.length-1]間選擇一個沒選過的索引i。
- 將nums[i]換成[nums[i]-k, nums[i]+k]之間的任意一個數。
定義一個陣列的美麗值為由單一元素組成的最長子序列長度。
求任意次操作後,nums的最大美麗值為多少。
注意:每個索引只能執行一次操作。
解法
x可以變成[x-k, x+k]之間的任意數。
反過來說,介於[x-k, x+k]之間的數都可以變成x。
能夠變成x的數字共有size=1+k*2種。
枚舉右邊界right,維護大小為size的滑動窗口。窗口內的所有元素都可以變成相同數,並組成子序列。
時間複雜度O(N + MX),其中MX為max(nums)。
空間複雜度O(MX)。
如果MX範圍太大,可能要考慮用雜湊表維護出現次數。
class Solution:
def maximumBeauty(self, nums: List[int], k: int) -> int:
MX=max(nums)
size=k*2+1
cnt=[0]*(MX+1)
for x in nums:
cnt[x]+=1
ans=0
left=0
sm=0
for right in range(MX+1):
sm+=cnt[right]
while right-left+1>size:
sm-=cnt[left]
left+=1
ans=max(ans,sm)
return ans
延續上述思路,若窗口最小值為x,則最大值為x+2*k。
將nums排序後,枚舉每個元素nums[i],用二分搜找到最後一個nums[i]+2*k的位置,這些元素全都屬於相同區間。
時間複雜度O(N log N)。
空間複雜度O(1)。
class Solution:
def maximumBeauty(self, nums: List[int], k: int) -> int:
nums.sort()
ans=0
for i,x in enumerate(nums):
j=bisect_right(nums,x+k*2)-1
ans=max(ans,j-i+1)
return ans
或是不用二分,直接雙指針維護最大差不超過2*k的滑動窗口也可以。
雖然時間瓶頸依然在於排序,但是找區間的部分會快一些。
class Solution:
def maximumBeauty(self, nums: List[int], k: int) -> int:
nums.sort()
ans=0
left=0
for right,x in enumerate(nums):
while x-nums[left]>2*k:
left+=1
ans=max(ans,right-left+1)
return ans