每一个查询的最大美丽值 图解题解

商品带价格和美丽值，每个预算到底求什么

items 每件商品是一对数：价格和美丽值；queries 每个数是一次查询的预算。对每个预算，在价格不超过它的商品里挑出最大美丽值，凑不出记 0，返回和 queries 等长的答案数组。题面 items=[[1,2],[3,2],[2,4],[5,6],[3,5]]、queries=[1,2,3,4,5,6]，答案是 [2,4,5,5,6,6]。

一个查询扫一趟商品，慢在哪一步

笨办法是一个查询扫一趟商品：拿这预算把 n 件商品逐个比过去，价格达标的就用它的美丽值刷新当前最大。可 m 个查询各扫一趟，总比较数 O(n×m)；商品和查询都到十万量级，乘起来上百亿次，超时。浪费在重复：预算变大，上轮达标的商品又得从头确认。

预算从小到大处理，指针为什么能不回头

让预算从小到大处理，重复确认就能省掉——预算只增不减，上一轮够格的商品这轮必然还够格，指针停在哪儿，下轮从哪儿往前，不退回。为此先把商品按价格升序排好，查询也按预算升序处理（这步叫离线：先把所有查询攒齐、重排后统一处理，不来一个答一个）。查询一重排，它在答案数组里的原位置就乱了，排序时要带上每个查询的原始下标，好把答案填回本来的格子。

指针只管前进，mx 和答案各自怎么落位

维护两个量：指针 i 指下一件待考察的商品，mx 记当前够格商品的最大美丽值，跨查询都不重置。轮到预算 q，让 i 往前走，只要 items[i] 价格 ≤ q 就纳入、用它的美丽值更新 mx、i 进一格；一碰到价格超 q 的商品就停，它右边只会更贵、买不起。此刻的 mx 就是这预算的答案，按记下的原始下标填回答案数组。下一个更大的预算接着用现在的 i 和 mx，不重来。

题面这五件商品，六个预算逐个走一遍

排序后商品价格排成 1、2、3、3、5，对应美丽值 2、4、2、5、6（价格 3 两件，美丽值 2 和 5）。查询本就升序。预算 1：头一件价格 1≤1，mx=2，i 走到 1；价格 2>1 停，ans[0]=2。预算 2：价格 2≤2，mx=4，i 走到 2；价格 3>2 停，ans[1]=4。预算 3：价格 3≤3 但美丽值 2 不及 4，mx 仍是 4，i 走到 3；又一件价格 3≤3 美丽值 5，mx=5，i 走到 4；价格 5>3 停，ans[2]=5。预算 4：价格 5>4 停，ans[3]=5。预算 5：价格 5≤5，mx=6，i 走到 5 到头，ans[4]=6。预算 6：i 已到头，ans[5]=6。答案 [2,4,5,5,6,6]。

排序吞掉扫描后，哪几处一松手就填错

两次排序主导：商品排序 O(n log n)，查询带下标排序 O(m log m)；之后指针 i 和查询各走一趟，共 O(n+m)，被吞掉。额外空间是下标数组 O(m)。几处一松手就出错：排序打乱了查询次序，按扫描序直接输出会填错格子，得写回原始下标；指针 i 跨查询只进不退，每题从头扫会退回 O(n×m)；判定用价格 ≤ 预算，严格小于会漏掉价格正好等于预算的商品；查不到商品时答案是 0，mx 从 0 起就满足，别返回 -1。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:
        items.sort()
        n, m = len(items), len(queries)
        ans = [0] * len(queries)
        i = mx = 0
        for q, j in sorted(zip(queries, range(m))):
            while i < n and items[i][0] <= q:
                mx = max(mx, items[i][1])
                i += 1
            ans[j] = mx
        return ans

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {
        sort(items.begin(), items.end());
        int n = items.size();
        int m = queries.size();
        vector<int> idx(m);
        iota(idx.begin(), idx.end(), 0);
        sort(idx.begin(), idx.end(), [&](int i, int j) {
            return queries[i] < queries[j];
        });
        int mx = 0, i = 0;
        vector<int> ans(m);
        for (int j : idx) {
            while (i < n && items[i][0] <= queries[j]) {
                mx = max(mx, items[i][1]);
                ++i;
            }
            ans[j] = mx;
        }
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public int[] maximumBeauty(int[][] items, int[] queries) {
        Arrays.sort(items, (a, b) -> a[0] - b[0]);
        int n = items.length;
        int m = queries.length;
        int[] ans = new int[m];
        Integer[] idx = new Integer[m];
        for (int i = 0; i < m; ++i) {
            idx[i] = i;
        }
        Arrays.sort(idx, (i, j) -> queries[i] - queries[j]);
        int i = 0, mx = 0;
        for (int j : idx) {
            while (i < n && items[i][0] <= queries[j]) {
                mx = Math.max(mx, items[i][1]);
                ++i;
            }
            ans[j] = mx;
        }
        return ans;
    }
}