力扣2503.矩阵查询可获得的最大分数
-
离线算法 + 排序 + 小根堆
- 将query数组从小到大排序，用小根堆存每个单元格的值
- 从小到大遍历query，如果堆顶元素小于query[i]，弹出，直到全部弹出，总弹出个数为答案
-
class Solution {int dx[4] = {0,1,0,-1},dy[4] = {1,0,-1,0};public:vector<int> maxPoints(vector<vector<int>>& grid, vector<int>& queries) {int k = queries.size(),id[k];iota(id,id+k,0);sort(id,id+k,[&](int i,int j){return queries[i] < queries[j];});vector<int> ans(k);priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> pq;pq.emplace(grid[0][0],0,0);grid[0][0] = 0;int m = grid.size(),n = grid[0].size(),cnt=0;for(int qi:id){//堆顶元素更小int q = queries[qi]; //tuple的语法，get<0>(tuple) 返回tuple的第一个元素的引用while(!pq.empty() && get<0>(pq.top()) < q){cnt ++;auto[_,tx,ty] = pq.top();pq.pop();for(int i=0;i<4;i++){int x = tx + dx[i],y = ty + dy[i];if (0 <= x && x < m && 0 <= y && y < n && grid[x][y]) {pq.emplace(grid[x][y],x,y);grid[x][y] = 0;}}}ans[qi] = cnt;}return ans;}};
