力扣2503.矩阵查询可获得的最大分数

力扣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;
        }
    };