leetcode 给我错误超过时间限制

Question

问题

2070。每个查询最美丽的项目

给定一个 2D 整数数组 items，其中 items[i] = [price i, beauty i] 分别表示商品的价格和美观。

您还会获得一个 0 索引的整数数组查询。对于每个查询[j]，您想要确定价格小于或等于查询[j]的商品的最大美感。如果不存在这样的项目，则此查询的答案为 0。

返回与查询长度相同的数组答案，其中answer[j]是

j.th

查询的答案。

示例1：

输入：items = [[1,2],[3,2],[2,4],[5,6],[3,5]]，querys = [1,2,3,4,5, 6]
输出：[2,4,5,5,6,6]
说明：

• 对于查询[0]=1，[1,2]是唯一有价格的项目<= 1. Hence, the answer for this query is 2.
• 对于查询[1]=2，可以考虑的项是[1,2]和[2,4]。 其中美度最高为4。
• 对于查询[2]=3和查询[3]=4，可以考虑的项是[1,2]、[3,2]、[2,4]和[3,5]。 其中美度最高为5。
• 对于querys[4]=5和querys[5]=6，可以考虑所有项目。 因此，他们的答案是所有物品中最大的美丽，即 6。 示例2：

输入：项目 = [[1,2],[1,2],[1,3],[1,4]]，查询 = [1]
输出：[4]
说明：
每件商品的价格都等于1，所以我们选择颜值最高的商品4。

请注意，多个商品可以具有相同的价格和/或外观。

/*
 * @param {number[][]} items
 * @param {number[]} queries
 * @return {number[]}
 */
var maximumBeauty = function (items, queries) {

    const result = [];

    // Loop over each query
    for (let q = 0; q < queries.length; q++) {
        const queryPrice = queries[q];
        let maxBeauty = 0; // Initialize maxBeauty to 0 for each query

        // Loop over each item to find items with price <= queryPrice
        for (let i = 0; i < items.length; i++) {
            const price = items[i][0];
            const beauty = items[i][1];
            
            // Check if item's price is within the query's limit
            if (price <= queryPrice) {
                // Update maxBeauty if this item's beauty is greater
                maxBeauty = Math.max(maxBeauty, beauty);
            }
        }
        
        // After looping through all items, store the maxBeauty for this query
        result.push(maxBeauty);

    }

    return  result  // Should output: [2, 4, 5, 5, 6, 6]
};

Answer 1

您的算法使用两个嵌套的 for 循环运行，这暗示了

O(n^2)

，而它可以通过不超过 2 次完成。

考虑这些问题，你几乎总是必须弄清楚如何使用 Set 或 Map（对象键/值也可以）。

我不想说更多 - 不要放弃解决方案，想一想，我相信你能找到答案！