力扣 第 386 场周赛 解题报告 | 反悔贪心

力扣 第 386 场周赛 解题报告 | 反悔贪心

前言

整体评价

前两天发烧，今天才补完题（非常惭愧）第三题的二分不容易想到，第四题的 “反悔堆” 这种思想值得学习。

T1 分割数组

思路：通过哈希表保证不存在出现两次以上的数即可。

时间复杂度： $O(n)$

class Solution:
    def isPossibleToSplit(self, nums: List[int]) -> bool:
        cnt = Counter()
        for x in nums:
            cnt[x] += 1
            if (cnt[x] > 2):
                return False
        return True

T2 求交集区域内的最大正方形面积

思路：交集左下角纵坐标为两个矩形左下角纵坐标的最大值，右上角纵坐标为两个矩形右上角纵坐标的最小值。排序遍历求解。

时间复杂度： $O(n^2)$

class Solution:
    def largestSquareArea(self, bottomLeft: List[List[int]], topRight: List[List[int]]) -> int:
        ans = 0
        n = len(bottomLeft)
        z = zip(bottomLeft, topRight)

        z = sorted(z)

        bottomLeft, topRight = zip(*z)

        for i in range(n):
            for j in range(i + 1, n):
                x1, y1 = max(bottomLeft[i][0], bottomLeft[j][0]), max(bottomLeft[i][1], bottomLeft[j][1])
                x2, y2 = min(topRight[i][0], topRight[j][0]), min(topRight[i][1], topRight[j][1])
                d = min(x2 - x1, y2 - y1)
                d = max(d, 0)
                ans = max(ans, d * d)
        
        return ans

(代码丑陋，欢迎批评指正)

T3 标记所有下标的最早秒数 I

思路：二分答案。从左往右遍历，判断是否可以完成任务。

时间复杂度： $O(log(m))$

class Solution:
    def earliestSecondToMarkIndices(self, nums, changeIndices) -> int:
        n, m = len(nums), len(changeIndices)
        s = sum(nums)

        def check(end):
            last_t = [-1] * n
            for i, x in enumerate(changeIndices[:end]):
                last_t[x-1] = i 
            if -1 in last_t:
                return False
            
            cnt = 0
            for i, x in enumerate(changeIndices[:end]): 
                idx = x - 1
                if i == last_t[idx]:
                    if cnt < nums[idx]:
                        return False 
                    cnt -= nums[idx]
                else:
                    cnt += 1 
            return True 

        ans = bisect_left(range(0, m + 1), True, key=check)
        return ans if ans <= m else -1

T4 标记所有下标的最早秒数 II

思路大致是无论当前的选项是否最优都接受，然后进行比较，如果选择之后不是最优了，则反悔，舍弃掉这个选项；否则，正式接受。如此往复。

这道题思维比较大，写的浑浑噩噩，终于改好了。

时间复杂度： $O(mlog(mn))$

class Solution:
    def earliestSecondToMarkIndices(self, nums: List[int], changeIndices: List[int]) -> int:
        n, m = len(nums), len(changeIndices)
        total = n + sum(nums)
        
        ft = [-1] * (n)
        for i in range(m-1, -1, -1):
            ft[changeIndices[i]-1] = i
        
        # 长度为 mx
        def check(mx: int) -> bool:
            slow = total
            cnt = 0
            h = []
            for i in range(mx-1, -1, -1):
                idx = changeIndices[i] - 1
                v = nums[idx]
                if i != ft[idx] or v <= 1:
                    cnt += 1
                    continue                
                if cnt == 0:
                    if not h or v <= h[0]:
                        cnt += 1
                        continue 
                    cnt += 2
                    slow += heappop(h) + 1
                slow -= v + 1
                cnt -= 1
                heappush(h, v)
            return cnt >= slow
        
        ans = bisect_left(range(0, m+1), True, key=check)

        return ans if ans < m + 1 else -1