2940 找到Alice和Bob可以相遇的建筑 (944/951)超时
class Solution {
public:vector<int> leftmostBuildingQueries(vector<int>& heights, vector<vector<int>>& queries) {//如果两个人一开始就在同一个建筑，返回当前数组下标//创建一个临时数组 最后返回它vector<int> v;for(int i=0;i<queries.size();i++){//如果两人下标相同 不超过heights长度if (queries[i][0] == queries[i][1]&&queries[i][0]<heights.size()){ v.push_back(queries[i][0]); //同时进入到下一个分支 以后尽量少使用goto语句 容易造成意想不到的错误goto next;}else{//确定queries中更大的数 作为数组下标//greaterNum = ;//如果可以直接跳转到比较大的身上if(heights[max(queries[i][0],queries[i][1])]>heights[min(queries[i][0],queries[i][1])]){v.push_back(max(queries[i][0],queries[i][1]));goto next;}for(int j = max(queries[i][0],queries[i][1])+1;j<heights.size();j++){//此处出错 比较应该是比较更大的heights中的元素 而不是下标if(heights[j]>max(heights[queries[i][0]],heights[queries[i][1]])){v.push_back(j);goto next;}}}v.push_back(-1);
next:}return v;}
}; 优化这段代码,让时间复杂度减小
是的，针对你的问题，可以考虑以下几种优化的方法来提高效率，尤其是当查询数量 mm 和建筑数量 nn 非常大的时候：
1. 单调栈（Monotonic Stack）：
通过使用单调栈，你可以在 O(n)O(n) 的时间内预处理每个建筑右侧第一个比它高的建筑索引。具体步骤如下：
- 遍历建筑数组
heights，使用一个栈来存储建筑索引。 - 当遇到当前建筑比栈顶建筑高时，出栈并记录该建筑的“下一个更高建筑”的索引。
时间复杂度：预处理的时间复杂度为 O(n)O(n)，每个查询的时间复杂度为 O(1)O(1)，总时间复杂度为 O(n+m)O(n+m)。
2. 二分搜索：
将建筑的高度存储为一个数组后，可以使用二分搜索来快速回答每个查询：
- 预处理：将建筑高度排序。
- 对于每个查询，使用二分搜索找到右侧第一个比较高的建筑。
时间复杂度：预处理 O(nlogn)O(nlogn)，每次查询 O(logn)O(logn)，总时间复杂度为 O(nlogn+mlogn)O(nlogn+mlogn)。
3. Segment Tree 或 Binary Indexed Tree：
构造一个线段树或树状数组（Binary Indexed Tree），以支持快速的区间查询来寻找最大值。
- 每个查询可以在 O(logn)O(logn) 的时间复杂度内完成。
- 预处理构造的时间复杂度为 O(n)O(n)。
时间复杂度：总时间复杂度仍然为 O(n+mlogn)O(n+mlogn)。
4. 动态规划：
如果建筑之间的关系可以通过某种逻辑规则进行构建，不妨考虑动态规划来保存已计算的结果，以避免重复计算。
5.总结：
以上这些方法都是在不同场景下的选择。最推荐的方法是使用单调栈，这种方式简单有效，并且可以在 O(n+m)O(n+m) 的时间复杂度中解决问题。根据具体的需求和数据特点，你可以选择最合适的方案。