Hard
题目描述
给你一个 m x n 的整数矩阵 grid 和一个大小为 k 的数组 queries。
找到一个大小为 k 的数组 answer，使得对于每个整数 queries[i]，你从矩阵的左上角单元格开始，重复以下过程：
- 如果
queries[i]严格大于你当前所在单元格的值，那么如果这是你第一次访问这个单元格，你可以获得一分，并且可以移动到上下左右四个方向的任意相邻单元格。 - 否则，你无法获得任何分数，结束这个过程。
经过这个过程，answer[i] 是你能够获得的最大分数。注意对于每个查询，你可以多次访问同一个单元格。
返回结果数组 answer。
示例 1：
输入：grid = [[1,2,3],[2,5,7],[3,5,1]], queries = [5,6,2]
输出：[5,8,1]
解释：上图显示了我们为每个查询访问哪些单元格来获得分数。
示例 2：
输入：grid = [[5,2,1],[1,1,2]], queries = [3]
输出：[0]
解释：我们无法获得任何分数，因为左上角单元格的值已经大于等于 3。
提示：
m == grid.lengthn == grid[i].length2 <= m, n <= 10004 <= m * n <= 10^5k == queries.length1 <= k <= 10^41 <= grid[i][j], queries[i] <= 10^6
解题思路
这道题的核心思路是将所有查询按从小到大排序，然后使用BFS逐步扩展可访问区域。
思路分析：
离线处理查询：由于所有查询都是提前给定的，我们可以将查询按值从小到大排序，这样就能复用之前的计算结果。
BFS渐进扩展：从左上角开始，使用最小堆维护边界上的所有待访问单元格。对于每个查询值，我们只需要将堆中小于该查询值的单元格都加入到可访问区域中。
优化策略：
- 使用优先队列（最小堆）来维护边界单元格，确保每次都处理值最小的单元格
- 通过visited数组避免重复访问同一个单元格
- 利用查询的单调性，前一个查询的结果可以作为下一个查询的起点
具体步骤：
- 将查询和其原始索引配对后排序
- 初始化优先队列，将起始点(0,0)加入
- 对于每个查询，从堆中取出所有值小于查询值的单元格，将其邻居加入堆中
- 统计已访问的单元格数量作为答案
这种方法的优势是避免了重复计算，时间复杂度相对较低。
代码实现
class Solution {
public:
vector<int> maxPoints(vector<vector<int>>& grid, vector<int>& queries) {
int m = grid.size(), n = grid[0].size();
int k = queries.size();
// 将查询和原始索引配对并排序
vector<pair<int, int>> sortedQueries;
for (int i = 0; i < k; i++) {
sortedQueries.push_back({queries[i], i});
}
sort(sortedQueries.begin(), sortedQueries.end());
vector<int> answer(k);
vector<vector<bool>> visited(m, vector<bool>(n, false));
// 优先队列存储 {值, 行, 列}
priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> pq;
// 如果起始点可以访问，加入队列
if (grid[0][0] < sortedQueries[0].first) {
pq.push({grid[0][0], 0, 0});
}
int points = 0;
int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for (auto& query : sortedQueries) {
int queryVal = query.first;
int originalIndex = query.second;
// 处理所有小于当前查询值的单元格
while (!pq.empty() && pq.top()[0] < queryVal) {
auto curr = pq.top();
pq.pop();
int val = curr[0], row = curr[1], col = curr[2];
if (visited[row][col]) continue;
visited[row][col] = true;
points++;
// 探索邻居
for (int i = 0; i < 4; i++) {
int newRow = row + directions[i][0];
int newCol = col + directions[i][1];
if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && !visited[newRow][newCol]) {
pq.push({grid[newRow][newCol], newRow, newCol});
}
}
}
answer[originalIndex] = points;
}
return answer;
}
};
class Solution:
def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:
import heapq
m, n = len(grid), len(grid[0])
k = len(queries)
# 将查询和原始索引配对并排序
sorted_queries = sorted((queries[i], i) for i in range(k))
answer = [0] * k
visited = [[False] * n for _ in range(m)]
# 优先队列存储 (值, 行, 列)
pq = []
# 如果起始点可以访问，加入队列
if grid[0][0] < sorted_queries[0][0]:
heapq.heappush(pq, (grid[0][0], 0, 0))
points = 0
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
for query_val, original_index in sorted_queries:
# 处理所有小于当前查询值的单元格
while pq and pq[0][0] < query_val:
val, row, col = heapq.heappop(pq)
if visited[row][col]:
continue
visited[row][col] = True
points += 1
# 探索邻居
for dr, dc in directions:
new_row, new_col = row + dr, col + dc
if (0 <= new_row < m and 0 <= new_col < n and
not visited[new_row][new_col]):
heapq.heappush(pq, (grid[new_row][new_col], new_row, new_col))
answer[original_index] = points
return answer
public class Solution {
public int[] MaxPoints(int[][] grid, int[] queries) {
int m = grid.Length, n = grid[0].Length;
int k = queries.Length;
// 将查询和原始索引配对并排序
var sortedQueries = queries.Select((q, i) => new { Value = q, Index = i })
.OrderBy(x => x.Value)
.ToArray();
int[] answer = new int[k];
bool[,] visited = new bool[m, n];
// 优先队列存储 {值, 行, 列}
var pq = new SortedSet<(int val, int row, int col)>();
// 如果起始点可以访问，加入队列
if (grid[0][0] < sortedQueries[0].Value) {
pq.Add((grid[0][0], 0, 0));
}
int points = 0;
int[,] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
foreach (var query in sortedQueries) {
int queryVal = query.Value;
int originalIndex = query.Index;
// 处理所有小于当前查询值的单元格
while (pq.Count > 0 && pq.Min.val < queryVal) {
var curr = pq.Min;
pq.Remove(curr);
int val = curr.val, row = curr.row, col = curr.col;
if (visited[row, col]) continue;
visited[row, col] = true;
points++;
// 探索邻居
for (int i = 0; i < 4; i++) {
int newRow = row + directions[i, 0];
int newCol = col + directions[i, 1];
if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && !visited[newRow, newCol]) {
pq.Add((grid[newRow][newCol], newRow, newCol));
}
}
}
answer[originalIndex] = points;
}
return answer;
}
}
var maxPoints = function(grid, queries) {
const m = grid.length, n = grid[0].length;
const k = queries.length;
// 将查询和原始索引配对并排序
const sortedQueries = queries.map((q, i) => [q, i]).sort((a, b) => a[0] - b[0]);
const answer = new Array(k);
const visited = Array(m).fill().map(() => Array(n).fill(false));
// 优先队列（最小堆）
const pq = new MinPriorityQueue({ priority: x => x[0] });
// 如果起始点可以访问，加入队列
if (grid[0][0] < sortedQueries[0][0]) {
pq.enqueue([grid[0][0], 0, 0]);
}
let points = 0;
const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
for (const [queryVal, originalIndex] of sortedQueries) {
// 处理所有小于当前查询值的单元格
while (!pq.isEmpty() && pq.front().element[0] < queryVal) {
const [val, row, col] = pq.dequeue().element;
if (visited[row][col]) continue;
visited[row][col] = true;
points++;
// 探索邻居
for (const [dr, dc] of directions) {
const newRow = row + dr;
const newCol = col + dc;
if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && !visited[newRow][newCol]) {
pq.enqueue([grid[newRow][newCol], newRow, newCol]);
}
}
}
answer[originalIndex] = points;
}
return answer;
};
复杂度分析
| 复杂度类型 | 值 |
|---|---|
| 时间复杂度 | O(mn log(mn) + k log k) |
| 空间复杂度 | O(mn + k) |
说明：
- 时间复杂度：每个单元格最多入队和出队一次，优先队列操作为 O(log(mn))，查询排序为 O(k log k)
- 空间复杂度：visited数组占用 O(mn)，优先队列最多存储 O(mn) 个元素，查询数组占用 O(k)
相关题目
. Trapping Rain Water II (Hard)
. Escape the Spreading Fire (Hard)