不知道哪一天的
2593. Find Score of an Array After Marking All Elements
就照做 用priority queue
看别人写O(N) 但我看不是很懂 懒得研究了 对不起
def findScore(self, nums: List[int]) -> int:
st = set()
hp = []
for i,num in enumerate(nums):
heappush(hp, (num, i))
ans = 0
while hp:
cur_num, cur_idx = heappop(hp)
if cur_idx not in st:
ans += cur_num
st.add(cur_idx)
st.add(cur_idx-1)
st.add(cur_idx+1)
return ans
不知道哪一天的
2762. Continuous Subarrays
鸡掰
就感觉卡在一个地方想不出来
偷偷看关键字
用两个monotonic queue去maintain subarr的maximum跟minimum
然后加以操作
有点刁钻
def continuousSubarrays(self, nums: List[int]) -> int:
l=0
ans=0
increaseD, decreaseD = deque(), deque()
for r in range(len(nums)):
while increaseD and nums[increaseD[-1]]>=nums[r]:
increaseD.pop()
while decreaseD and nums[decreaseD[-1]]<=nums[r]:
decreaseD.pop()
decreaseD.append(r)
increaseD.append(r)
while nums[decreaseD[0]]-nums[increaseD[0]]>2:
l += 1
if decreaseD[0]<l:
decreaseD.popleft()
if increaseD[0]<l:
increaseD.popleft()
ans += (r-l+1)
return ans
不知道哪一天的
1792. Maximum Average Pass Ratio
就一样pq硬搞
懒得想其他方法了
写得有点杂乱
def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) ->
float:
pq = []
for idx, classs in enumerate(classes):
heappush(pq, (classs[0]/classs[1]-(classs[0]+1)/(classs[1]+1), idx))
for _ in range(extraStudents):
_, idx = heappop(pq)
classes[idx][0] += 1
classes[idx][1] += 1
heappush(pq,
(classes[idx][0]/classes[idx][1]-(classes[idx][0]+1)/(classes[idx][1]+1),
idx))
return sum([passs/total for passs,total in classes])/len(classes)
今天的hard晚点有空再说
但大机率懒得搞 对不起