map|二分查找|离线查询|LeetCode:2736最大和查询-阿里云开发者社区

题目

给你两个长度为 n 、下标从 0 开始的整数数组 nums1 和 nums2 ，另给你一个下标从 1 开始的二维数组 queries ，其中 queries[i] = [xi, yi] 。

对于第 i 个查询，在所有满足 nums1[j] >= xi 且 nums2[j] >= yi 的下标 j (0 <= j < n) 中，找出 nums1[j] + nums2[j] 的最大值，如果不存在满足条件的 j 则返回 -1 。

返回数组 answer ，其中 answer[i] 是第 i 个查询的答案。

示例 1：

输入：nums1 = [4,3,1,2], nums2 = [2,4,9,5], queries = [[4,1],[1,3],[2,5]]

输出：[6,10,7]

解释：

对于第 1 个查询：xi = 4 且 yi = 1 ，可以选择下标 j = 0 ，此时 nums1[j] >= 4 且 nums2[j] >= 1 。nums1[j] + nums2[j] 等于 6 ，可以证明 6 是可以获得的最大值。

对于第 2 个查询：xi = 1 且 yi = 3 ，可以选择下标 j = 2 ，此时 nums1[j] >= 1 且 nums2[j] >= 3 。nums1[j] + nums2[j] 等于 10 ，可以证明 10 是可以获得的最大值。

对于第 3 个查询：xi = 2 且 yi = 5 ，可以选择下标 j = 3 ，此时 nums1[j] >= 2 且 nums2[j] >= 5 。nums1[j] + nums2[j] 等于 7 ，可以证明 7 是可以获得的最大值。

因此，我们返回 [6,10,7] 。

示例 2：

输入：nums1 = [3,2,5], nums2 = [2,3,4], queries = [[4,4],[3,2],[1,1]]

输出：[9,9,9]

解释：对于这个示例，我们可以选择下标 j = 2 ，该下标可以满足每个查询的限制。

示例 3：

输入：nums1 = [2,1], nums2 = [2,3], queries = [[3,3]]

输出：[-1]

解释：示例中的查询 xi = 3 且 yi = 3 。对于每个下标 j ，都只满足 nums1[j] < xi 或者 nums2[j] < yi 。因此，不存在答案。

参数范围：

nums1.length == nums2.length

n == nums1.length

1 <= n <= 10⁵

1 <= nums1[i], nums2[i] <= 10⁹

1 <= queries.length <= 10⁵

queries[i].length == 2

xi == queries[i][1]

yi == queries[i][2]

1 <= xi, yi <= 10⁹

离线查询、值降序map

时间复杂度😮（nlogn)。

按xi的降序对queries的索引排序。

变量解析


maxHeap	记录所有的nums1[j]和nums2[j]，nums1[j]大的在堆顶
ySum	记录所有nums[j]大于当前xi的nums2[j]和nums1[j]+nums2[j]，键升序，值降序。如果 nums2[j1] <= nums2[j2]且nums1[j1]+nums2[j1] <=nums1[j2]+nums2[j2]。则j1被j2淘汰了。
it	[it,ySum.m_map.end()) 中的元素，全部大于xi和yi，由于值是降序，所有第一个值就是答案。

代码

核心代码

template<class _Kty,class _Ty,bool bValueDdes,bool bOutSmallKey> 
class COrderValueMap 
{
public:
  void Add (_Kty key, _Ty value)
  {
    if (bOutSmallKey)
    {
      if (bValueDdes)
      {
        AddOutSmall(key, value, std::less_equal<_Ty>(), std::greater_equal<_Ty>());
      }
      else
      {
        AddOutSmall(key, value, std::greater_equal<_Ty>(), std::less_equal<_Ty>());
      }
    }
    else 
    {
      if (bValueDdes)
      {
        AddNotOutSmall(key, value, std::greater_equal<_Ty>(), std::less_equal<_Ty>());
      }
      else
      {
        AddNotOutSmall(key, value, std::less_equal<_Ty>(), std::greater_equal<_Ty>());
      }
    }
  };
  std::map<_Kty, _Ty> m_map;
protected:
  template<class _Pr1, class _Pr2>
  void AddOutSmall(_Kty key, _Ty value, _Pr1 pr1, _Pr2 pr2)
  {
    auto it = m_map.lower_bound(key);
    if ((m_map.end() != it) && pr1(it->second, value))
    {
      return;//被旧值淘汰
    }
    auto ij = it;
    while (it != m_map.begin())
    {
      --it;
      if (pr2(it->second, value))
      {
        it = m_map.erase(it);
      }
    }
    m_map[key] = value;
  }
  template<class _Pr1, class _Pr2>
  void AddNotOutSmall(_Kty key, _Ty value, _Pr1 pr1,_Pr2 pr2 )
  {
    auto it = m_map.upper_bound(key);
    if ((m_map.begin() != it) && pr1(std::prev(it)->second, value))
    {
      return;//被淘汰
    }
    auto ij = it;
    for (; (m_map.end() != ij) && pr2(ij->second, value); ++ij);
    m_map.erase(it, ij);
    m_map[key] = value;
  };
};

class Solution {
public:
  vector<int> maximumSumQueries(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {
    vector<int> indexs(queries.size());
    iota(indexs.begin(), indexs.end(), 0);
    sort(indexs.begin(), indexs.end(), [&](const int i1, const int i2) {return queries[i1][0] > queries[i2][0]; });
    priority_queue<pair<int, int>> maxHeap;
    for (int i = 0; i < nums1.size(); i++)
    {
      maxHeap.emplace(nums1[i], nums2[i]);
    }
    COrderValueMap<int, int, false, true> ySum;
    vector<int> vRet(queries.size(), -1);
    for (const auto i : indexs)
    {
      while (maxHeap.size() && (maxHeap.top().first >= queries[i][0]))
      {
        ySum.Add(maxHeap.top().second, maxHeap.top().first + maxHeap.top().second);
        maxHeap.pop();
      }
      auto it = ySum.m_map.lower_bound(queries[i][1]);
      if (ySum.m_map.end() != it)
      {
        vRet[i] = it->second;
      }
    }
    return vRet;
  }
};

测试用例

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
  if (v1.size() != v2.size())
  {
    assert(false);
    return;
  }
  for (int i = 0; i < v1.size(); i++)
  {
    assert(v1[i] == v2[i]);
  }
}
template<class T>
void Assert(const T& t1, const T& t2)
{
  assert(t1 == t2);
}
int main()
{
  vector<int> nums1, nums2;
  vector<vector<int>> queries;
  {
    Solution slu;   
    nums1 = { 4,3,1,2 }, nums2 = { 2,4,9,5 }, queries = { {4,1},{1,3},{2,5} };
    auto res = slu.maximumSumQueries(nums1,nums2,queries);
    Assert(vector<int>{6, 10, 7}, res);
  }
  {
    Solution slu;
    nums1 = { 3,2,5 }, nums2 = { 2,3,4 }, queries = { {4,4},{3,2},{1,1} };
    auto res = slu.maximumSumQueries(nums1, nums2, queries);
    Assert(vector<int>{9, 9, 9}, res);
  }
  {
    Solution slu;
    nums1 = { 2,1 }, nums2 = { 2,3 }, queries = { {3,3} };
    auto res = slu.maximumSumQueries(nums1, nums2, queries);
    Assert(vector<int>{-1}, res);
  }
}

2023年6月代码

class CMaxLineTreeMap
{
public:
CMaxLineTreeMap(int iArrSize) :m_iArrSize(iArrSize)
{
}
//iIndex 从0开始
void Modify(int iIndex, int iValue)
{
Modify(1, 1, m_iArrSize, iIndex + 1, iValue);
}
//iNeedQueryLeft iNeedQueryRight 从0开始
int Query(const int iNeedQueryLeft, const int iNeedQueryRight)
{
return Query(1, 1, m_iArrSize, iNeedQueryLeft + 1, iNeedQueryRight + 1);
}
protected:
int Query(const int iTreeNodeIndex, const int iRecordLeft, const int iRecordRight, const int iNeedQueryLeft, const int iNeedQueryRight)
{
if ((iNeedQueryLeft <= iRecordLeft) && (iNeedQueryRight >= iRecordRight))
{
return m_mData[iTreeNodeIndex];
}
const int iMid = (iRecordLeft + iRecordRight) / 2;
int iRet = 0;
if (iNeedQueryLeft <= iMid)
{
iRet = Query(iTreeNodeIndex * 2, iRecordLeft, iMid, iNeedQueryLeft, iNeedQueryRight);
}
if (iNeedQueryRight > iMid)
{
iRet = max(iRet, Query(iTreeNodeIndex * 2 + 1, iMid + 1, iRecordRight, iNeedQueryLeft, iNeedQueryRight));
}
return iRet;
}
void Modify(int iTreeNodeIndex, int iLeft, int iRight, int iIndex, int iValue)
{
if (iLeft == iRight)
{
m_mData[iTreeNodeIndex] = max(m_mData[iTreeNodeIndex],iValue);
return;
}
const int iMid = (iLeft + iRight) / 2;
if (iIndex <= iMid)
{
Modify(iTreeNodeIndex * 2, iLeft, iMid, iIndex, iValue);
}
else
{
Modify(iTreeNodeIndex * 2 + 1, iMid + 1, iRight, iIndex, iValue);
}
m_mData[iTreeNodeIndex] = max(m_mData[iTreeNodeIndex * 2], m_mData[iTreeNodeIndex * 2 + 1]);
}
const int m_iArrSize;
std::unordered_map m_mData;
};
class Solution {
public:
vector maximumSumQueries(vector& nums1, vector& nums2, vector& queries) {
m_c = queries.size();
vector indexs;
for (int i = 0; i < m_c; i++)
{
indexs.emplace_back(i);
}
std::sort(indexs.begin(), indexs.end(), [&queries](const int&i1, const int& i2)
{
return queries[i1][1] > queries[i2][1];
});
std::multimap> m_Num2ToNum1Sum;
for (int i = 0; i < nums2.size(); i++)
{
m_Num2ToNum1Sum.emplace(nums2[i], std::make_pair(nums1[i], nums1[i] + nums2[i]));
}
vector vRet(m_c);
auto it = m_Num2ToNum1Sum.rbegin();
const int iMaxValue = 1000 * 1000 * 1000;
CMaxLineTreeMap lineTree(iMaxValue+1);
for (int index = 0; index < indexs.size(); index++)
{
const int i = indexs[index];
const auto& que = queries[i];
while ((it != m_Num2ToNum1Sum.rend()) && (it->first >= que[1]))
{
lineTree.Modify(it->second.first, it->second.second);
it++;
}
vRet[i] = lineTree.Query(que[0], iMaxValue);
if (0 == vRet[i])
{
vRet[i] = -1;
}
}
return vRet;
}
int m_c;
};

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。

https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程

https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者操作系统：win10 开发环境： VS2022 C++17

如无特殊说明，本算法用**C++**实现。

map|二分查找|离线查询|LeetCode:2736最大和查询

题目