给定一个数字，说 'KEY' 和 map <int, int> myMap。我试图在地图 myMap 中找到最小的键 k（条件：k < KEY），使其值最大。
例子：
map <int, int> myMap = {{3,1}, {4,3}, {5,2}, {6,3}, {7,2}, {8,5}};
// ^^^
int KEY = 7;
答案是 4，因为对于所有小于 7(KEY) 的键，键 4 和键 6 的最大值都是 3。4 是最小的键。
地图动态增加，有几个这样的查询与 KEY。
我试图在 O(logN) 时间内获得 {k,v} 对
使用lower_bound后我被卡住了。使用下限给我最大'k'，使得k < KEY。在上面的示例中，我可以为 KEY=7 获得 {7,2}。但是努力在 logN 时间内达到 {4,3}。是否有任何数据结构可以帮助我在 logN 时间内实现这一目标？
更新：
我确保也在对数时间内对地图进行更新。整数不超过 10^5。是否可以使用其他一些数据结构和方法（在这种情况下它看起来像动态规划/二进制搜索）来在对数时间内解决这个问题？
这个怎么样。您维护一个次要地图，它是主要地图的一个子集。具体来说，{k, v}当且仅当主映射中所有较小的键对应于较小的值时，此辅助映射才会包含。
对于您的示例{3,1}, {4,3}, {5,2}, {6,3}, {7,2}, {8,5}，此辅助地图将是{3,1}, {4,3}, {8,5}. 观察值如何随着键单调增加。
如何使用此映射来回答问题应该是显而易见的 - 只需使用lower_bound. 在示例中，对于 7 的键，查找将找到 4，即正确答案。
现在，如何维护这张地图。当您插入{k, v}主地图时，使用 查找k次要地图lower_bound。有两种可能：
存在具有相等或更大值的较小键。什么都不做，二级地图不需要更新。
不存在较小的键，或者较小的键对应较小的值。然后
{k, v}二级地图k直到遇到k'具有较大值的键，或到达终点。擦除k和k'（不包括两者）或从k（不包括）到结尾的范围。从表面上看，这最后一步看起来是线性的 - 但实际上它是摊销常数。在N插入过程中，此步骤2*N最多必须遍历元素（例如，N-1第一步每个插入一个元素，最后一步删除所有元素并插入一个）。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句