本文涉及的基础知识点

二分查找算法合集
离线查询

LeetCode2940题目

给你一个下标从 0 开始的正整数数组 heights ，其中 heights[i] 表示第 i 栋建筑的高度。
如果一个人在建筑 i ，且存在 i < j 的建筑 j 满足 heights[i] < heights[j] ，那么这个人可以移动到建筑 j 。
给你另外一个数组 queries ，其中 queries[i] = [ai, bi] 。第 i 个查询中，Alice 在建筑 ai ，Bob 在建筑 bi 。
请你能返回一个数组 ans ，其中 ans[i] 是第 i 个查询中，Alice 和 Bob 可以相遇的 最左边的建筑 。如果对于查询 i ，Alice 和 Bob 不能相遇，令 ans[i] 为 -1 。
示例 1：
输入：heights = [6,4,8,5,2,7], queries = [[0,1],[0,3],[2,4],[3,4],[2,2]]
输出：[2,5,-1,5,2]
解释：第一个查询中，Alice 和 Bob 可以移动到建筑 2 ，因为 heights[0] < heights[2] 且 heights[1] < heights[2] 。
第二个查询中，Alice 和 Bob 可以移动到建筑 5 ，因为 heights[0] < heights[5] 且 heights[3] < heights[5] 。
第三个查询中，Alice 无法与 Bob 相遇，因为 Alice 不能移动到任何其他建筑。
第四个查询中，Alice 和 Bob 可以移动到建筑 5 ，因为 heights[3] < heights[5] 且 heights[4] < heights[5] 。
第五个查询中，Alice 和 Bob 已经在同一栋建筑中。
对于 ans[i] != -1 ，ans[i] 是 Alice 和 Bob 可以相遇的建筑中最左边建筑的下标。
对于 ans[i] == -1 ，不存在 Alice 和 Bob 可以相遇的建筑。
示例 2：
输入：heights = [5,3,8,2,6,1,4,6], queries = [[0,7],[3,5],[5,2],[3,0],[1,6]]
输出：[7,6,-1,4,6]
解释：第一个查询中，Alice 可以直接移动到 Bob 的建筑，因为 heights[0] < heights[7] 。
第二个查询中，Alice 和 Bob 可以移动到建筑 6 ，因为 heights[3] < heights[6] 且 heights[5] < heights[6] 。
第三个查询中，Alice 无法与 Bob 相遇，因为 Bob 不能移动到任何其他建筑。
第四个查询中，Alice 和 Bob 可以移动到建筑 4 ，因为 heights[3] < heights[4] 且 heights[0] < heights[4] 。
第五个查询中，Alice 可以直接移动到 Bob 的建筑，因为 heights[1] < heights[6] 。
对于 ans[i] != -1 ，ans[i] 是 Alice 和 Bob 可以相遇的建筑中最左边建筑的下标。
对于 ans[i] == -1 ，不存在 Alice 和 Bob 可以相遇的建筑。
参数范围：
1 <= heights.length <= 5 * 104
1 <= heights[i] <= 109
1 <= queries.length <= 5 * 104
queries[i] = [ai, bi]
0 <= ai, bi <= heights.length - 1

分析

时间复杂度

时间复杂度(nlogm)，枚举queries时间复杂度O(n)，处理单个查询时间复杂度O(logm)。n和queries的长度,m是heights的长度。

分情况讨论

无需考虑一个人跳两次及以上的情况。假定跳了两次: i1->i2->i3，那说明i1<i2,i2<i3，也就是i1<i3，那直接跳到i3就可以了。
三种情况：

	两人都不跳，初始位置相同
	一人直接跳到另外一个人处
	两个人都跳

两个人都跳

假定两人的最大位置是iMaxIndex，两人的最大高度是iMaxHeight。heights(iMaxIndex…]中寻找大于iMaxHeight的组合， 如果存在多个组合，返回最小的索引。
mHeightIndexs的key是高度，value是索引。如果key1 >= key0，且value1 <= value0，那key0被淘汰。
淘汰后，key和value都升序。

离线查询

如果iMaxIndex是按降序排列，那么mHeightIndexs每个元素只需要插入一次。

代码

核心代码

class Solution {
public:
vector leftmostBuildingQueries(vector& heights, vector<vector>& queries) {
m_c = queries.size();
vector indexs;
for (int i = 0; i < m_c; i++)
{
indexs.emplace_back(i);
}
sort(indexs.begin(), indexs.end(), [&](const int& i1, const int& i2)
{
return max(queries[i1][0], queries[i1][1]) > max(queries[i2][0], queries[i2][1]);
});
COrderValueMap<int,int,true,true> mHeightIndexs;
vector vRet(m_c, -1);
int iHeightIndex = heights.size() - 1;
for (int inx :indexs)
{
const int iMinIndex = min(queries[inx][0], queries[inx][1]);
const int iMaxIndex = max(queries[inx][0], queries[inx][1]);
if (iMinIndex == iMaxIndex) {
vRet[inx] = iMaxIndex;
continue;
}
if (heights[iMinIndex] < heights[iMaxIndex])
{
vRet[inx] = iMaxIndex;
continue;
}
const int iMaxHeight = max(heights[queries[inx][0]], heights[queries[inx][1]]);
while (iHeightIndex > iMaxIndex)
{
mHeightIndexs.Add(heights[iHeightIndex], iHeightIndex);
iHeightIndex–;
}
auto it = mHeightIndexs.m_map.upper_bound(iMaxHeight);
if (mHeightIndexs.m_map.end() != it)
{
vRet[inx] = it->second;
}
}
return vRet;
}
int m_c;
};

测试用例

template
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}

template
void Assert(const vector& v1, const vector& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
Assert(v1[i], v2[i]);
}
}

int main()
{
vectorheights;
vector<vector> queries;
int k;
vector res;
{
Solution slu;
heights = {6, 4, 8, 5, 2, 7};
queries = { {0, 1}, { 0,3 }, { 2,4 }, { 3,4 }, { 2,2 }};
res = slu.leftmostBuildingQueries(heights, queries);
//Assert(1, res);
}

//CConsole::Out(res);

}

离线+线段树 2025年9月8

令两位玩家分别在i1,i2。如果$i1==i2$，则查询结果就是i1。
性质一：i1,i2互换，并不影响查询结果。故$i1>i2$，则交换之。
如果能够从i1跳到i2，则查询结果是i2。否则求 heights[i2$\cdots$]中大于max(heigts[i1],height[i2])的最小下标。
sg[heights[i]]记录搞定为heghts[i]的最小下标。
按i2的降序处理各查询。

线段树

区间查询 单点修改 离散化后静态开点
回调类：最小最小值。

template<class TSave, class TSet >
class ISegmentTreeCall
{
public:
	virtual void OnUnion(TSave& unionVal, const TSave& leftVal, const TSave& rVal, int leftIndex, int mid, int rIndex) = 0;
};

template<class TSave, class TSet >
class ISingleSegmentTreeCall : public ISegmentTreeCall<TSave,TSet>
{
public:
	virtual void OnUpdateLeaf(TSave& save, int iSaveIndex, const TSet& update) = 0;
};

template<class TSave, class TSet >
class IRangleSegmentTreeCall : public ISingleSegmentTreeCall<TSave, TSet>
{
public:
	virtual void OnUnionSet(TSet& oldBuff, const TSet& newBuff) = 0;
	virtual void OnUpdateBranch(TSave& save, int iLeftIndex, int iRightIndex, const TSet& update) = 0;
};

template<class TSave = int, class TSet = int >
class CMinMinSegmentTreeCall :public IRangleSegmentTreeCall <TSave, TSet> {
public:
	virtual void OnUpdateLeaf(TSave& save, int iSaveIndex, const TSet& update)
	{
		save = min(save, update);
	}
	virtual void OnUnion(TSave& unionVal, const TSave& leftVal, const TSave& rVal, int leftIndex, int mid, int rIndex) {
		unionVal = min(leftVal, rVal);
	}
	virtual void OnUnionSet(TSet& oldBuff, const TSet& newBuff) {
		oldBuff = min(oldBuff, newBuff);
	}
	virtual void OnUpdateBranch(TSave& save, int iLeftIndex, int iRightIndex, const TSet& update) {
		save = min(save, update);
	}
};

template<class TSave, class TSet >
class CSegmentTree {
public:
	CSegmentTree(ISegmentTreeCall<TSave, TSet>& call, TSave tDefault)
		:m_call(call), m_tDefault(tDefault) {}
	TSave Query(int left, int r) {
		return Query(left, r, m_tDefault);
	}
	TSave Query(int left, int r, TSave tDefault) {
		TSave ans = tDefault;
		std::function<void(const TSave&, const int&, const int&)> fun = [&](const TSave& cur, const int& leftIndex, const int& rIndex) {
			m_call.OnUnion(ans, ans, cur, left, leftIndex - 1, rIndex);
		};
		Enum(left, r, fun);
		return ans;
	}
	virtual void Enum(int leftIndex, int leftRight, std::function<void(const TSave&, const int&, const int&)>& fun) = 0;
	virtual TSave QueryAll() = 0;
protected:
	ISegmentTreeCall<TSave, TSet>& m_call;
	const TSave m_tDefault;
};


template<class TSave, class TSet >
class CSingeSegmentTree :public CSegmentTree<TSave, TSet>
{
public:
	CSingeSegmentTree(ISingleSegmentTreeCall<TSave, TSet>& call, TSave tDefault)
		:m_call(call), CSegmentTree<TSave, TSet>(call, tDefault) {}
	virtual void Update(int index, TSet update) = 0;
protected:
	ISingleSegmentTreeCall<TSave, TSet>& m_call;
};
template<class TSave, class TSet >
class CSingeTreeSegmentTree : public CSingeSegmentTree<TSave, TSet>
{
protected:
	struct CTreeNode
	{
		TSave data;
		CTreeNode* m_lChild = nullptr, * m_rChild = nullptr;
		~CTreeNode() {
			delete m_lChild; m_lChild = nullptr;
			delete m_rChild; m_rChild = nullptr;
		}
	};
	CTreeNode* m_root;
	const int m_iMinIndex, m_iMaxIndex;
public:
	CSingeTreeSegmentTree(int iMinIndex, int iMaxIndex, ISingleSegmentTreeCall<TSave, TSet>& call, TSave tDefault) :CSingeSegmentTree<TSave, TSet>(call, tDefault)
		, m_iMinIndex(iMinIndex), m_iMaxIndex(iMaxIndex) {
		m_root = CreateNode();
	}
	void Update(int index, TSet update) override {
		if ((index < m_iMinIndex) || (index > m_iMaxIndex)) { return; }
		Update(m_root, m_iMinIndex, m_iMaxIndex, index, update);
	}
	TSave QueryAll() override {
		return m_root->data;
	}
	//void OnQuery(TSave& ans, const TSave& cur, const int& iSaveLeft, const int& iSaveRight);
	void Enum(int iQueryLeft, int iQueryRight, std::function<void(const TSave&, const int&, const int&)>& fun)override {
		if (max(iQueryLeft, m_iMinIndex) > min(iQueryRight, m_iMaxIndex)) { return; }//和根节点没交集
		Enum(m_root, m_iMinIndex, m_iMaxIndex, iQueryLeft, iQueryRight, fun);
	}
	~CSingeTreeSegmentTree() {
		delete m_root;
	}
protected:
	void Enum(CTreeNode* node, int iSaveLeft, int iSaveRight, int iQueryLeft, int iQueryRight, std::function<void(const TSave&, const int&, const int&)>& fun) {
		if ((iQueryLeft <= iSaveLeft) && (iSaveRight <= iQueryRight)) {
			fun(node->data, iSaveLeft, iSaveRight);
			return;
		}
		CreateChilds(node);
		const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
		if (mid >= iQueryLeft) {
			Enum(node->m_lChild, iSaveLeft, mid, iQueryLeft, iQueryRight, fun);
		}
		if (mid + 1 <= iQueryRight) {
			Enum(node->m_rChild, mid + 1, iSaveRight, iQueryLeft, iQueryRight, fun);
		}
	}
	void Update(CTreeNode* node, int iSaveLeft, int iSaveRight, int iUpdateNO, TSet update) {
		if (iSaveLeft == iSaveRight) {
			CSingeSegmentTree<TSave, TSet>::m_call.OnUpdateLeaf(node->data, iUpdateNO, update);
			return;
		}
		CreateChilds(node);
		const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
		if (iUpdateNO <= mid)
		{
			Update(node->m_lChild, iSaveLeft, mid, iUpdateNO, update);
		}
		else {
			Update(node->m_rChild, mid + 1, iSaveRight, iUpdateNO, update);
		}
		CSingeSegmentTree<TSave, TSet>::m_call.OnUnion(node->data, node->m_lChild->data, node->m_rChild->data, iSaveLeft, mid, iSaveRight);
	}
	CTreeNode* CreateNode() {
		CTreeNode* node = new CTreeNode;
		node->data = this->m_tDefault;
		return node;
	}
	void CreateChilds(CTreeNode* node) {
		if (nullptr != node->m_lChild) { return; }
		node->m_lChild = CreateNode();
		node->m_rChild = CreateNode();
	}
};

template<class TSave, class TSet >
class CSingleVectorSegmentTree : public CSingeSegmentTree<TSave, TSet>
{
public:
	CSingleVectorSegmentTree(int iEleSize, ISingleSegmentTreeCall<TSave, TSet>& call, TSave tDefault) :
		m_iEleSize(iEleSize), CSingeSegmentTree<TSave, TSet>(call, tDefault), m_save(iEleSize * 4, tDefault) {

	}
	void Update(int index, TSet update) override {
		if ((index < 0) || (index >= m_iEleSize)) { return; }
		Update(1, 0, m_iEleSize - 1, index, update);
	}
	TSave QueryAll() override {
		return m_save[1];
	}
	virtual void Enum(int iQueryLeft, int iQueryRight, std::function<void(const TSave&, const int&, const int&)>& fun) override {
		if (max(iQueryLeft, 0) > min(iQueryRight, m_iEleSize - 1)) { return; }//和根节点没交集
		Enum(1, 0, m_iEleSize - 1, iQueryLeft, iQueryRight, fun);
	}
	void swap(CSingleVectorSegmentTree& o) {
		m_save.swap(o.m_save);
	}
protected:
	const int m_iEleSize;
	/*	void Init(std::function<void(TSave&, const int&)> fun, int iNodeNO, int iSaveLeft, int iSaveRight)
		{
			if (iSaveLeft == iSaveRight) {
				fun(m_save[iNodeNO], iSaveLeft);
				return;
			}
			const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
			Init(fun, iNodeNO * 2, iSaveLeft, mid);
			Init(fun, iNodeNO * 2 + 1, mid + 1, iSaveRight);
			this->OnUpdateParent(m_save[iNodeNO], m_save[iNodeNO * 2], m_save[iNodeNO * 2 + 1], iSaveLeft, iSaveRight);
		}*/
	void Enum(int iNodeNO, int iSaveLeft, int iSaveRight, int iQueryLeft, int iQueryRight, std::function<void(const TSave&, const int&, const int&)>& fun) {
		if ((iSaveLeft >= iQueryLeft) && (iSaveRight <= iQueryRight)) {
			fun(m_save[iNodeNO], iSaveLeft, iSaveRight);
			return;
		}
		const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
		if (mid >= iQueryLeft) {
			Enum(iNodeNO * 2, iSaveLeft, mid, iQueryLeft, iQueryRight, fun);
		}
		if (mid + 1 <= iQueryRight) {
			Enum(iNodeNO * 2 + 1, mid + 1, iSaveRight, iQueryLeft, iQueryRight, fun);
		}
	}
	void Update(int iNodeNO, int iSaveLeft, int iSaveRight, int iUpdateNO, TSet update) {
		if (iSaveLeft == iSaveRight)
		{
			CSingeSegmentTree<TSave, TSet>::m_call.OnUpdateLeaf(m_save[iNodeNO], iSaveLeft, update);
			return;
		}
		const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
		if (iUpdateNO <= mid) {
			Update(iNodeNO * 2, iSaveLeft, mid, iUpdateNO, update);
		}
		else {
			Update(iNodeNO * 2 + 1, mid + 1, iSaveRight, iUpdateNO, update);
		}
		CSegmentTree<TSave, TSet>::m_call.OnUnion(m_save[iNodeNO], m_save[iNodeNO * 2], m_save[iNodeNO * 2 + 1], iSaveLeft, mid, iSaveRight);
	}
	vector<TSave> m_save;
};

template<class T=int>
class CDiscretize //离散化
{
public:
	CDiscretize(vector<T> nums)
	{
		sort(nums.begin(), nums.end());
		nums.erase(std::unique(nums.begin(), nums.end()), nums.end());
		m_nums = nums;
		for (int i = 0; i < nums.size(); i++)
		{
			m_mValueToIndex[nums[i]] = i;
		}
	}
	int operator[](const T value)const
	{
		auto it = m_mValueToIndex.find(value);
		if (m_mValueToIndex.end() == it)
		{
			return -1;
		}
		return it->second;
	}
	int size()const
	{
		return m_mValueToIndex.size();
	}
	vector<T> m_nums;
protected:	
	unordered_map<T, int> m_mValueToIndex;
};

class Solution {
		public:
			vector<int> leftmostBuildingQueries(vector<int>& heights, vector<vector<int>>& queries) {
				CDiscretize<int> dis(heights);
				for (auto& n : heights) {
					n = dis[n];
				}
				const int N = heights.size(),M = queries.size();
				for (auto& v : queries) {
					if (v[0] > v[1]) { swap(v[0], v[1]); }
				}
				vector<int> inxs(M),ans(M);
				iota(inxs.begin(), inxs.end(), 0);
				sort(inxs.begin(), inxs.end(), [&](const int i1, const int i2) {return queries[i1][1] > queries[i2][1];});
				CMinMinSegmentTreeCall<int, int> call;
				CSingleVectorSegmentTree<int, int> sg(dis.size(), call, INT_MAX/2);
				int j = heights.size() - 1;
				for (const auto& i : inxs) {
					const int a = queries[i][0], b = queries[i][1];
					while (j >b ) {
						sg.Update(heights[j], j);
						j--;
					}
					if (a == b) {
						ans[i] = a;
						continue;
					}
					if (heights[a] < heights[b]) {
						ans[i] = b;
						continue;
					}
					const int c = sg.Query(max(heights[a], heights[b])+1, dis.size() - 1);
					ans[i] = (c > N) ? -1:c;
				}
				return ans;
			}
		};

扩展阅读

视频课程

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

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
墨子曰：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛