thảo luận Leetcode mỗi ngày

var maximumBeauty = function (items, queries) {
    const sorted = [...items].sort((u, v) => {
        return u[0] - v[0] || v[1] - u[1];
    });
    items.length = 0;
    for (const item of sorted) {
        if (!items.length || item[1] > items[items.length-1][1]) {
            items.push(item);
        }
    }
    return queries.map(q => {
        const idx = _.sortedLastIndexBy(items, [q], '0');
        console.log({ q, idx });
        return idx ? items[idx-1][1] : 0;
    });
};

function maximumBeauty(items: number[][], q: number[]): number[] {
    items.sort((a, b) => a[0] - b[0] || b[1] - a[1]);
   
    const maxList: number[][] = [];
    let curMax = 0;
    for (const [u, v] of items) {
        curMax = Math.max(curMax, v);
        maxList.push([u, curMax]);
    }

    const res: number[] = [];
    for (const p of q) {
        let l = 0, r = maxList.length;
        while (l < r) {
            const m = l + Math.floor((r - l) / 2);
            if (maxList[m][0] > p) {
                r = m;
            } else {
                l = m + 1;
            }
        }

        const cur = l > 0 ? maxList[l - 1][1] : 0;
        res.push(cur);
    }

    return res;
}

class Solution:
    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:
        items.sort()
        prev_max_beauty = 0
        for item in items:
            prev_max_beauty = item[1] = max(item[1], prev_max_beauty)

        res = []
        for query in queries:
            l, r = 0, len(items)
            while l < r:
                mid = (l + r)//2
                if items[mid][0] <= query:
                    l = mid + 1
                else:
                    r = mid
            if l == 0:
                res.append(0)
            else:
                res.append(items[l - 1][1])
        
        return res

class Solution(object):
    def maximumBeauty(self, items, queries):
        items.sort(key = lambda x: (x[0], -x[1]))
        cur_max = items[0][1]
        n = len(items)
        for i in range(n):
            cur_max = max(cur_max, items[i][1])
            items[i][1] = cur_max

        def search(num):
            l, r = 0, n - 1
            while l <= r:
                mid = (l + r) // 2
                if items[mid][0] > num:
                    r = mid - 1
                else:
                    l = mid + 1
            return items[r][1] if r >= 0 else 0

        return [search(i) for i in queries]

func binarySearch(num int, arr [][]int) int {
    low, high := 0, len(arr)-1
    found := -1

    for low <= high {
        mid := (low + high) / 2
        if arr[mid][0] <= num {
            found = mid
            low = mid + 1
        } else {
            high = mid - 1
        }
    }

    return found
}

func maximumBeauty(items [][]int, queries []int) []int {
    sort.Slice(items, func(i, j int) bool {
        return items[i][0] < items[j][0]
    })

    n := len(items)
    maxBeauty := make([]int, n)
    maxBeauty[0] = items[0][1]

    for i := 1; i < n; i++ {
        if items[i][1] > maxBeauty[i-1] {
            maxBeauty[i] = items[i][1]
        } else {
            maxBeauty[i] = maxBeauty[i-1]
        }
    }

    results := make([]int, len(queries))
    memo := make(map[int]int)

    for i, val := range queries {
        if cachedValue, exists := memo[val]; exists {
            results[i] = cachedValue
            continue
        }

        j := binarySearch(val, items)

        if j == -1 {
            results[i] = 0
            memo[val] = 0
        } else {
            results[i] = maxBeauty[j]
            memo[val] = maxBeauty[j]
        }
    }

    return results
}

class Solution {
public:
    vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {
        auto queryMap = map<int, vector<int>>();
        for (auto i = 0; i < queries.size(); ++i) { queryMap[queries[i]].push_back(i); }

        sort(items.begin(), items.end(), [](const vector<int>& item_a, const vector<int>& item_b) {
            return item_a[0] < item_b[0];
        });

        auto itemIter = items.begin(); auto currentMaxBeauty = 0;
        auto maxBeauties = vector<int>(queries.size(), 0);
        for (const auto& priceIndexes : queryMap) {
            for (; itemIter < items.end() && (*itemIter)[0] <= priceIndexes.first; ++itemIter) {
                if (currentMaxBeauty < (*itemIter)[1]) currentMaxBeauty = (*itemIter)[1];
            }
            for (const auto& j : priceIndexes.second) {
                maxBeauties[j] = currentMaxBeauty;
            }
        }
        return maxBeauties;
    }
};

class Solution {
    public int[] maximumBeauty(int[][] items, int[] queries) {
        int nq = queries.length, cMaxB = 0, rs[] = new int[nq];
        Arrays.sort(items, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
        var tm = new TreeMap<Integer, Integer>();
        for (int[] e : items) if (cMaxB < e[1]) tm.put(e[0], cMaxB = e[1]);
        for (int i = 0; i < nq; i++) {
            var e = tm.floorEntry(queries[i]);
            if (e != null) rs[i] = e.getValue();
        }
        return rs;
    }
}

class Solution {
public:
    vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {
        int n = items.size();
        int m = queries.size();

        sort(items.begin(), items.end(), [] (const vector<int> &i1, const vector<int> &i2) {
            return i1[0] < i2[0];
        });

        vector<int> query_indexes(m);
        iota(query_indexes.begin(), query_indexes.end(), 0);
        sort(query_indexes.begin(), query_indexes.end(), [&queries] (const int &i, const int &j) {
            return queries[i] < queries[j];
        });

        vector<int> res(m);
        int p_items = 0;
        int max_beauty = 0;

        for (const int &index : query_indexes) {
            int query = queries[index];
            while (p_items < n && items[p_items][0] <= query) {
                max_beauty = max(max_beauty, items[p_items][1]);
                ++p_items;
            }
            res[index] = max_beauty;
        }
        return res;
    }
};

class Solution:
    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:
        items = sorted(items)
        queries = sorted([(queries[i], i) for i in range(len(queries))])
        ans = [0] * len(queries)

        i, max_beautiful = 0, 0
        for [q, j] in queries:
            while i < len(items) and items[i][0] <= q:
                max_beautiful = max(max_beautiful, items[i][1])
                i += 1
            ans[j] = max_beautiful

        return ans

class Solution {
    public static final int PRICE = 0;
    public static final int BEAUTY = 1;
    public int[] maximumBeauty(int[][] items, int[] queries) {
        Arrays.sort(items, new Comparator<int[]> () {
            @Override
            public int compare(int[] itemA, int[] itemB) {
                return itemA[PRICE] - itemB[PRICE];
            }
        });

        int[] maxBeautyAt = new int[items.length];
        int maximumBeauty = 0;
        int index = 0;
        for (int[] item : items) {
            maximumBeauty = Math.max(
                maximumBeauty,
                item[BEAUTY]
            );
            maxBeautyAt[index] = maximumBeauty;
            index++;
        }

        int[] answer = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int queryPrice = queries[i];
            int lastItem = lowerBoundPriceItem(items, queryPrice);
            answer[i] = (lastItem == -1) ? 0 : maxBeautyAt[lastItem];
        }

        return answer;
    }

    public int lowerBoundPriceItem(int[][] items, int queryPrice) {
        int found = -1;
        int left = 0, right = items.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (items[mid][PRICE] <= queryPrice) {
                found = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return found;
    }
}