题目描述
思路解析
一句话答案：LeetCode 2070 每个查询的最大美丽值把商品和查询都按价格排序，离线用单调指针推进、随手维护价格达标里的最大美丽值，一趟扫完所有查询。时间 O(n log n + m log m)、空间 O(m)。
商品带价格和美丽值，每个预算到底求什么
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。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢这套路:商品按价格排序,查询由小到大处理,指针 i 单调前进,mx 单调不减,答案随手就是当下的 mx。下面把这套动作一帧一帧演给你看。
原始输入 · 商品还没排序：先看原始输入。舞台这排格子写的是每件商品的美丽值,侧栏配上它们各自的价格。你会发现价格是乱的:1, 3, 2, 5, 3。价格乱着排,双指针没法一路只往前走,所以第一步必须先按价格把商品排好队。
第一步 · 把商品按价格升序排好：排序之后,商品的价格从小到大变成 1, 2, 3, 3, 5,格子里对应的美丽值是 2, 4, 2, 5, 6。注意价格 3 出现了两次,它们的美丽值分别是 2 和 5。侧栏也换成排好序的样子。从现在起,指针 i 从左往右扫,一路只会遇到价格越来越大的商品,这正是双指针能成立的前提。
查询 q = 1 · 从指针 i = 0 继续：开始处理查询序列 [1, 2, 3, 4, 5, 6]。本例查询本身就是升序,排好序后顺序不变,答案可以直接按顺序填。第一个预算是 1。接下来看还能不能纳入更多价格达标的商品。
纳入商品 0 · 价格 1 ≤ 1：看紫色这件商品 0,价格 1,没有超过预算 1,把它纳入候选。它的美丽值是 2,拿去和当前 mx = 0 取较大值。结果刷新成 2,更漂亮的商品出现了。指针 i 前进到 1。
停下 · 商品 1 价格 2 超预算：再看下一件商品 1,价格 2,已经大于预算 1了。它以及它右边的商品价格只会更贵,都买不起,循环就此停下。指针 i 就停在这里,留给下一个更大的预算接着用,不用回退。
记录 · answer[0] = 2：预算 1 的答案定了,就是此刻的 mx = 2,填进 answer 的第 0 位。注意下一个查询的预算更大,指针 i 和 mx 都从现在的状态接着走,前面纳入的商品一件都不用重看,这正是排序换来的好处。
查询 q = 2 · 从指针 i = 1 继续：轮到预算 2。指针 i 停在上一个查询留下的位置 1,绿色的商品是之前已经纳入的,mx 现在是 2。接下来看还能不能纳入更多价格达标的商品。
纳入商品 1 · 价格 2 ≤ 2：看紫色这件商品 1,价格 2,没有超过预算 2,把它纳入候选。它的美丽值是 4,拿去和当前 mx = 2 取较大值。结果刷新成 4,更漂亮的商品出现了。指针 i 前进到 2。
停下 · 商品 2 价格 3 超预算：再看下一件商品 2,价格 3,已经大于预算 2了。它以及它右边的商品价格只会更贵,都买不起,循环就此停下。指针 i 就停在这里,留给下一个更大的预算接着用,不用回退。
记录 · answer[1] = 4：预算 2 的答案定了,就是此刻的 mx = 4,填进 answer 的第 1 位。注意下一个查询的预算更大,指针 i 和 mx 都从现在的状态接着走,前面纳入的商品一件都不用重看,这正是排序换来的好处。
查询 q = 3 · 从指针 i = 2 继续：轮到预算 3。指针 i 停在上一个查询留下的位置 2,绿色的商品是之前已经纳入的,mx 现在是 4。接下来看还能不能纳入更多价格达标的商品。
纳入商品 2 · 价格 3 ≤ 3：看紫色这件商品 2,价格 3,没有超过预算 3,把它纳入候选。它的美丽值是 2,拿去和当前 mx = 4 取较大值。美丽值 2 没有 4 大,mx 保持 4 不变,但这件商品照样算已纳入,指针继续前移。指针 i 前进到 3。
纳入商品 3 · 价格 3 ≤ 3：看紫色这件商品 3,价格 3,没有超过预算 3,把它纳入候选。它的美丽值是 5,拿去和当前 mx = 4 取较大值。结果刷新成 5,更漂亮的商品出现了。指针 i 前进到 4。
停下 · 商品 4 价格 5 超预算：再看下一件商品 4,价格 5,已经大于预算 3了。它以及它右边的商品价格只会更贵,都买不起,循环就此停下。指针 i 就停在这里,留给下一个更大的预算接着用,不用回退。
记录 · answer[2] = 5：预算 3 的答案定了,就是此刻的 mx = 5,填进 answer 的第 2 位。注意下一个查询的预算更大,指针 i 和 mx 都从现在的状态接着走,前面纳入的商品一件都不用重看,这正是排序换来的好处。
查询 q = 4 · 从指针 i = 4 继续：轮到预算 4。指针 i 停在上一个查询留下的位置 4,绿色的商品是之前已经纳入的,mx 现在是 5。接下来看还能不能纳入更多价格达标的商品。
停下 · 商品 4 价格 5 超预算：再看下一件商品 4,价格 5,已经大于预算 4了。它以及它右边的商品价格只会更贵,都买不起,循环就此停下。指针 i 就停在这里,留给下一个更大的预算接着用,不用回退。
记录 · answer[3] = 5：预算 4 的答案定了,就是此刻的 mx = 5,填进 answer 的第 3 位。注意下一个查询的预算更大,指针 i 和 mx 都从现在的状态接着走,前面纳入的商品一件都不用重看,这正是排序换来的好处。
查询 q = 5 · 从指针 i = 4 继续：轮到预算 5。指针 i 停在上一个查询留下的位置 4,绿色的商品是之前已经纳入的,mx 现在是 5。接下来看还能不能纳入更多价格达标的商品。
纳入商品 4 · 价格 5 ≤ 5：看紫色这件商品 4,价格 5,没有超过预算 5,把它纳入候选。它的美丽值是 6,拿去和当前 mx = 5 取较大值。结果刷新成 6,更漂亮的商品出现了。指针 i 前进到 末尾。
停下 · 商品已全部纳入：指针 i 已经走到末尾,五件商品全被纳入候选,绿了一整排。没有新商品可看,循环停下。此刻的最大美丽值就是 6。
记录 · answer[4] = 6：预算 5 的答案定了,就是此刻的 mx = 6,填进 answer 的第 4 位。注意下一个查询的预算更大,指针 i 和 mx 都从现在的状态接着走,前面纳入的商品一件都不用重看,这正是排序换来的好处。
查询 q = 6 · 从指针 i = 末尾 继续：轮到预算 6。指针 i 停在上一个查询留下的位置 末尾,绿色的商品是之前已经纳入的,mx 现在是 6。接下来看还能不能纳入更多价格达标的商品。
停下 · 商品已全部纳入：指针 i 已经走到末尾,五件商品全被纳入候选,绿了一整排。没有新商品可看,循环停下。此刻的最大美丽值就是 6。
记录 · answer[5] = 6：预算 6 的答案定了,就是此刻的 mx = 6,填进 answer 的第 5 位。所有查询处理完毕,answer 收工。
回放 · answer = [2, 4, 5, 5, 6, 6]：六个查询全部处理完。答案数组是 [2, 4, 5, 5, 6, 6],和一开始预告的完全对上。回头看整条主线:商品按价格排好队,查询由小到大处理,指针 i 从头扫到尾只走了一趟,mx 一路只涨不跌,每个查询都直接读走当下的 mx。排序换来的就是这一趟不回头的扫描。
边界想清:预算不够记 0、同价取最大美丽值、价格等于预算用 ≤ 判定要能选中。
面试重点:可换前缀最大值加二分支持在线、查询排序是为了指针不回退、复杂度由排序主导。
参考代码
from __future__ import annotationsfrom 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复杂度
- 时间：O(n log n + m log m)，n 件商品排序 O(n log n),m 个查询按值排下标 O(m log m),这两次排序是主导;之后双指针扫描里指针 i 与查询各自只走一趟,合计 O(n + m),被排序吞没
- 空间：O(m)，按峰值算,不计输入与答案本身。为查询排序额外开一个长度 m 的下标数组;商品排序可原地进行。排序内部栈 C plus plus 与 Java 约 O(log n)、Python 最坏 O(n),量级不超过 O(n + m)
易错点
面试追问把动画讲成自己的话
追问除了离线排序加双指针,还有别的做法吗?
追问为什么非要把查询也排序?
追问复杂度到底是多少?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
咒语和药水的成功对数
LeetCode 2300 · 中等 · 沿着 二分套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题