【leetcode】2070.每一个查询的最大美丽值

题目描述

leetcode.cn/problems/…/description

思路

题目要求每次查询不超过一定价格下的最大美丽值, 那么可以先对价格进行排序.
排完序后在对前缀取一个最大值, 那么这个最大前缀就表示的是在这个价格下能买到的最大的美丽值了.

但是有了这个最大前缀之后还是有个问题, 前缀数组中的值并不与查询的值$queries[i]$对应, 对于这种散列的值就可以请出"二分"大法了.
虽然下标并不表示真正的值, 但是他还是跟真正的值有关系的, 因为他是由排完序的$items$数组得到的, 这个数组中记录了, 价格的大小, 可以通过$items$价格区间来确定查询的范围.

因为$items$已经是从小到大排序的了, 所以只需要知道$queries[i]$在$items$中对应的最右边那个位置的下标$pos$, 那么最大前缀数组的$f[pos]$就是可以获得的最大美丽值了.

代码

rust:

impl Solution {
    pub fn maximum_beauty(items: Vec<Vec<i32>>, queries: Vec<i32>) -> Vec<i32> {
        let mut items: Vec<Vec<i32>> = items;
        items.sort();

        let mut f: Vec<i32> = Vec::with_capacity(items.len() + 1);
        // with_capacity 虽然会预分配内存, 但是依旧是空向量, 需要 push
        f.push(0);
        for i in 0..(items.len()) {
            f.push(std::cmp::max(f[i], items[i][1]));
        }

        // 对 queries 中的每个数取可以取得在 items 中最右边的数
        queries
            .iter()
            .map(|&query: &i32| {
                // partition_point(|item: &Vec<i32>| item[0] <= query) 类似与 py 中的 bisect_right
                f[items.partition_point(|item: &Vec<i32>| item[0] <= query)]
            })
            .collect()
    }
}

py:

class Solution:
    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:
        items.sort(key=lambda x: x[0])
        f = [0] * (len(items) + 1)
        for i in range(len(items)):
            f[i + 1] = max(f[i], items[i][1])
        ans = []
        for i in queries:
            pos = bisect_right(items, i, key=lambda x: x[0])
            ans.append(f[pos])
        return ans