Leetcode 2070. Most Beautiful Item for Each Query [Python]

第一段写法会在第33个TC上TLE，还是不够优化。设置maxb，qdict的目的就是避免重复插入query里的值到items队列中。同时要注意，保留value小于等于某个值时，所出现过的最大美丽值。用来对应保留到items的value所能对应到的value小于等于当前值所能获得的最大美丽值。

class Solution:
    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:
        items.sort(key = lambda x:(x[0],-x[1]))
        res = []
        maxb = collections.defaultdict(int)
        largerbefore = float('-inf')
        newitems = []
        for p,b in items:
            largerbefore = max(largerbefore, b)
            maxb[p] = largerbefore
            if p not in newitems:
                newitems.append(p)
        qus = collections.Counter(queries)
        qdict = collections.defaultdict()
        for q in queries:
            if q in qdict:
                res.append(qdict[q])
                continue
            if q in newitems:
                res.append(maxb[q])
                qdict[q] = maxb[q]
            else:
                pos = bisect.bisect_left(newitems, q)
                if pos != 0:
                    res.append(maxb[newitems[pos-1]])
                    qdict[q] = maxb[newitems[pos-1]]
                else:
                    res.append(0)
                    qdict[q] = 0
        return res      

其实可以反过来想，只要这个item的v没法大过query里的钱数量，就可以继续用下一个相同value但排序后更靠后的item来对比，或者是用value更大的item来做对比，并更新第此刻的最大美丽值，赋值给对应位置的res上。

class Solution:
    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:
        N, M = len(items), len(queries)
        res = [_ for _ in range(M)]
        
        newqueries = [(queries[i], i) for i in range(M)]
        items.sort()
        newqueries.sort()
        
        largestbefore = 0
        j = 0
        for q, i in newqueries:
            res[i] = largestbefore
            while j < N and items[j][0] <= q:
                res[i] = max(res[i], items[j][1])
                j += 1
            largestbefore = res[i]
        return res