251周赛&&57双周赛好题分享

双周赛和周赛均是在国际服打的,双周赛A了两题,周赛A了三题。两场周赛都是在第二题浪费了很多时间并且WA了很多次。这两道题都是带一些细节的模拟题,可以看到自己在这种题上还是思维理的不是很顺,其实题目很简单。需要分享的是双周赛的后两题,难度不大,但是技巧很强,值得分享。

5806. 描述绘画结果

这个题很明显的差分数组,但是上来被这个区间整晕了,其实只要在查分计算的过程中判断一下是不是右侧边界,如果是右侧边界就需要分开。

class Solution:
def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:
diff = [0] * 100005
right = set()
for i in range(len(segments)):
diff[segments[i][0]] += segments[i][2]
diff[segments[i][1]] -= segments[i][2]
right.add(segments[i][1])
pre = -1
before = 1
ans = []
cur = 0
for i in range(1,100005):
cur += diff[i]
if pre == -1:
pre = cur
if cur != pre or i in right:
if pre!=0:
ans.append([before,i,pre])
before = i
pre = cur
return ans

5196. 队列中可以看到的人数

这个题是很典型的单调栈的应用,虽然代码量很短,但是其实要能想到反向遍历是要对单调栈吃的很透,这也可能是hard的原因,这个题和下一个最高的温度有点像,其实只有维护一个单调递减的栈就好了。

class Solution:
def canSeePersonsCount(self, heights: List[int]) -> List[int]:
stack = []
n = len(heights)
res = [0] * n
for i in range(n-1,-1,-1):
while stack and heights[stack[-1]] < heights[i]:
stack.pop()
res[i] += 1
if stack:
res[i] += 1
stack.append(i)
return res

TODO:周赛的最后一题