题目描述
思路解析动画文字版
记牢这套路:商品按价格排序,查询由小到大处理,指针 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题