2555.两个线段获得的最多奖品

链接：2555.两个线段获得的最多奖品
难度：Medium
标签：数组、二分查找、滑动窗口
简介：请你返回在选择两个最优线段的前提下，可以获得的 最多 奖品数目。

题解 1 - python

• 编辑时间：2024-09-12
• 执行用时：614ms
• 内存消耗：28.86MB
• 编程语言：python
• 解法介绍：遍历所有区间，并且统计非区间内的最大值

from sortedcontainers import SortedList
class Solution:
    def maximizeWin(self, prizePositions: List[int], k: int) -> int:
        n = len(prizePositions)
        arr1 = []
        i = 0
        while i < n:
            cnt = 1
            p = i
            while i + 1 < n and prizePositions[i + 1] == prizePositions[p]:
                cnt += 1
                i += 1
            arr1.append((prizePositions[i], cnt))
            i += 1
        n = len(arr1)
        arr2 = []
        r = 0
        cnt = 0
        for i in range(n):
            while r < n and arr1[r][0] <= arr1[i][0] + k:
                cnt += arr1[r][1]
                r += 1
            arr2.append(cnt)
            cnt -= arr1[i][1]
        arr3 = []
        l = n - 1
        cnt = 0
        for i in range(n - 1, -1, -1):
            while l >= 0 and arr1[l][0] >= arr1[i][0] - k:
                cnt += arr1[l][1]
                l -= 1
            arr3.append(cnt)
            cnt -= arr1[i][1]
        arr3.reverse()
    
        res = 0
        sl = SortedList(key=lambda i: arr3[i])
        sr = SortedList(key=lambda i: arr2[i])
        for i in range(n): sr.add(i)
        r = 0
        for i in range(n):
            val = arr2[i]
            while r < n and arr1[r][0] <= arr1[i][0] + k:
                sr.remove(r)
                r += 1
            val2 = 0
            if sl: val2 = max(val2, arr3[sl[-1]])
            if sr: val2 = max(val2, arr2[sr[-1]])
            res = max(res, val + val2)
            sl.add(i)
        return res