LeetCode 2070中等二分查找
每一个查询的最大美丽值 图解题解
这道题到底在问什么
给定二维数组 items,items[i] = 价格 与 美丽值;再给一个数组 queries。对每个查询 queries[j],求价格 ≤ queries[j] 的商品中最大的美丽值,不存在则记 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]
- 输入
- items=[[10,1000]], queries=[5]
- 输出
- [0] (没有价格 ≤ 5 的商品)
最优解：一步一步想明白
- 3记牢这套路:商品按价格排序,查询由小到大处理,指针 i 单调前进,mx 单调不减,答案随手就是当下的 mx。下面把这套动作一帧一帧演给你看。
- 4先看原始输入。舞台这排格子写的是每件商品的美丽值,侧栏配上它们各自的价格。你会发现价格是乱的:1, 3, 2, 5, 3。价格乱着排,双指针没法一路只往前走,所以第一步必须先按价格把商品排好队。
- 5排序之后,商品的价格从小到大变成 1, 2, 3, 3, 5,格子里对应的美丽值是 2, 4, 2, 5, 6。注意价格 3 出现了两次,它们的美丽值分别是 2 和 5。侧栏也换成排好序的样子。从现在起,指针 i 从左往右扫,一路只会遇到价格越来越大的商品,这正是双指针能成立的前提。
- 6开始处理查询序列 [1, 2, 3, 4, 5, 6]。本例查询本身就是升序,排好序后顺序不变,答案可以直接按顺序填。第一个预算是 1。接下来看还能不能纳入更多价格达标的商品。
- 7看紫色这件商品 0,价格 1,没有超过预算 1,把它纳入候选。它的美丽值是 2,拿去和当前 mx = 0 取较大值。结果刷新成 2,更漂亮的商品出现了。指针 i 前进到 1。
- 8再看下一件商品 1,价格 2,已经大于预算 1了。它以及它右边的商品价格只会更贵,都买不起,循环就此停下。指针 i 就停在这里,留给下一个更大的预算接着用,不用回退。
- 9预算 1 的答案定了,就是此刻的 mx = 2,填进 answer 的第 0 位。注意下一个查询的预算更大,指针 i 和 mx 都从现在的状态接着走,前面纳入的商品一件都不用重看,这正是排序换来的好处。
- 10轮到预算 2。指针 i 停在上一个查询留下的位置 1,绿色的商品是之前已经纳入的,mx 现在是 2。接下来看还能不能纳入更多价格达标的商品。
- 11看紫色这件商品 1,价格 2,没有超过预算 2,把它纳入候选。它的美丽值是 4,拿去和当前 mx = 2 取较大值。结果刷新成 4,更漂亮的商品出现了。指针 i 前进到 2。
- 12再看下一件商品 2,价格 3,已经大于预算 2了。它以及它右边的商品价格只会更贵,都买不起,循环就此停下。指针 i 就停在这里,留给下一个更大的预算接着用,不用回退。
- 13预算 2 的答案定了,就是此刻的 mx = 4,填进 answer 的第 1 位。注意下一个查询的预算更大,指针 i 和 mx 都从现在的状态接着走,前面纳入的商品一件都不用重看,这正是排序换来的好处。
- 14轮到预算 3。指针 i 停在上一个查询留下的位置 2,绿色的商品是之前已经纳入的,mx 现在是 4。接下来看还能不能纳入更多价格达标的商品。
- 15看紫色这件商品 2,价格 3,没有超过预算 3,把它纳入候选。它的美丽值是 2,拿去和当前 mx = 4 取较大值。美丽值 2 没有 4 大,mx 保持 4 不变,但这件商品照样算已纳入,指针继续前移。指针 i 前进到 3。
- 16看紫色这件商品 3,价格 3,没有超过预算 3,把它纳入候选。它的美丽值是 5,拿去和当前 mx = 4 取较大值。结果刷新成 5,更漂亮的商品出现了。指针 i 前进到 4。
- 17再看下一件商品 4,价格 5,已经大于预算 3了。它以及它右边的商品价格只会更贵,都买不起,循环就此停下。指针 i 就停在这里,留给下一个更大的预算接着用,不用回退。
- 18预算 3 的答案定了,就是此刻的 mx = 5,填进 answer 的第 2 位。注意下一个查询的预算更大,指针 i 和 mx 都从现在的状态接着走,前面纳入的商品一件都不用重看,这正是排序换来的好处。
- 19轮到预算 4。指针 i 停在上一个查询留下的位置 4,绿色的商品是之前已经纳入的,mx 现在是 5。接下来看还能不能纳入更多价格达标的商品。
- 20再看下一件商品 4,价格 5,已经大于预算 4了。它以及它右边的商品价格只会更贵,都买不起,循环就此停下。指针 i 就停在这里,留给下一个更大的预算接着用,不用回退。
- 21预算 4 的答案定了,就是此刻的 mx = 5,填进 answer 的第 3 位。注意下一个查询的预算更大,指针 i 和 mx 都从现在的状态接着走,前面纳入的商品一件都不用重看,这正是排序换来的好处。
- 22轮到预算 5。指针 i 停在上一个查询留下的位置 4,绿色的商品是之前已经纳入的,mx 现在是 5。接下来看还能不能纳入更多价格达标的商品。
- 23看紫色这件商品 4,价格 5,没有超过预算 5,把它纳入候选。它的美丽值是 6,拿去和当前 mx = 5 取较大值。结果刷新成 6,更漂亮的商品出现了。指针 i 前进到 末尾。
- 24指针 i 已经走到末尾,五件商品全被纳入候选,绿了一整排。没有新商品可看,循环停下。此刻的最大美丽值就是 6。
- 25预算 5 的答案定了,就是此刻的 mx = 6,填进 answer 的第 4 位。注意下一个查询的预算更大,指针 i 和 mx 都从现在的状态接着走,前面纳入的商品一件都不用重看,这正是排序换来的好处。
- 26轮到预算 6。指针 i 停在上一个查询留下的位置 末尾,绿色的商品是之前已经纳入的,mx 现在是 6。接下来看还能不能纳入更多价格达标的商品。
- 27指针 i 已经走到末尾,五件商品全被纳入候选,绿了一整排。没有新商品可看,循环停下。此刻的最大美丽值就是 6。
- 28预算 6 的答案定了,就是此刻的 mx = 6,填进 answer 的第 5 位。所有查询处理完毕,answer 收工。
- 29六个查询全部处理完。答案数组是 [2, 4, 5, 5, 6, 6],和一开始预告的完全对上。回头看整条主线:商品按价格排好队,查询由小到大处理,指针 i 从头扫到尾只走了一趟,mx 一路只涨不跌,每个查询都直接读走当下的 mx。排序换来的就是这一趟不回头的扫描。
⚠️ 容易写错的地方
✗ 错：排序打乱查询后,直接按扫描顺序输出答案
✓ 对：把答案写回每个查询的原始下标 j
排序改变了查询的次序,若不记录原下标,答案会对错位置;所以要么排 (值, 原下标),要么排一个下标数组
✗ 错：每个查询都从头重新扫一遍商品
✓ 对：指针 i 跨查询保留,只前进不回退
查询升序保证已纳入的商品对更大预算仍达标,重扫会把复杂度退化成 O(n × m)
✗ 错：用严格小于 价格 < 预算 判定
✓ 对：判定条件是价格 ≤ 预算
价格恰好等于预算的商品也买得起,用严格小于会漏掉它们
✗ 错：没有达标商品时返回 -1 或忘记赋值
✓ 对：mx 初始化为 0,查不到就是 0
题目规定不存在符合条件的商品时答案为 0,mx 从 0 起就天然满足
完整代码（Python / C++ / Java）
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 ansC++
#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;
}
}复杂度
时间
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)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 每一个查询的最大美丽值 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
除了离线排序加双指针,还有别的做法吗?+
有。把商品按价格排序后,对美丽值做一次前缀最大值预处理,得到「价格前 k 小的商品里最大美丽值」。对每个查询用二分找出最后一个价格 ≤ 预算的位置,直接读那个前缀最大值即可,复杂度 O((n + m) log n)。它的好处是查询之间互不依赖,天然支持在线查询,不必先攒齐所有查询。
为什么非要把查询也排序?+
为了让指针 i 单调不回退。如果查询乱序,一会儿大一会儿小,指针可能要来回移动,就享受不到均摊线性的好处。排序后查询由小到大,i 只进不退,扫描一趟到底。代价是要记住每个查询的原下标,好把答案填回正确位置。
复杂度到底是多少?+
时间由两次排序主导,商品排序 O(n log n),查询排序 O(m log m),双指针扫描 O(n + m) 被吞没。额外空间主要是查询的下标数组 O(m)。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 每一个查询的最大美丽值 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。