自己学做网站,大连建设工程信息网档案下载,新冠数据实时更新,网络工程师工资一般多少的作者推荐
【贪心算法】【中位贪心】.执行操作使频率分数最大
题目
有 n 个人排成一个队列#xff0c;从左到右 编号为 0 到 n - 1 。给你以一个整数数组 heights #xff0c;每个整数 互不相同#xff0c;heights[i] 表示第 i 个人的高度。 一个人能 看到 他右边另一个人…作者推荐
【贪心算法】【中位贪心】.执行操作使频率分数最大
题目
有 n 个人排成一个队列从左到右 编号为 0 到 n - 1 。给你以一个整数数组 heights 每个整数 互不相同heights[i] 表示第 i 个人的高度。 一个人能 看到 他右边另一个人的条件是这两人之间的所有人都比他们两人 矮 。更正式的第 i 个人能看到第 j 个人的条件是 i j 且 min(heights[i], heights[j]) max(heights[i1], heights[i2], …, heights[j-1]) 。 请你返回一个长度为 n 的数组 answer 其中 answer[i] 是第 i 个人在他右侧队列中能 看到 的 人数 。 示例 1 输入heights [10,6,8,5,11,9] 输出[3,1,2,1,1,0] 解释 第 0 个人能看到编号为 1 2 和 4 的人。 第 1 个人能看到编号为 2 的人。 第 2 个人能看到编号为 3 和 4 的人。 第 3 个人能看到编号为 4 的人。 第 4 个人能看到编号为 5 的人。 第 5 个人谁也看不到因为他右边没人。 示例 2 输入heights [5,1,2,3,10] 输出[4,1,1,1,0] 提示 n heights.length 1 n 105 1 heights[i] 105 heights 中所有数 互不相同 。
分析
从右向左遍历所有人(i从大到小,sta记录所有右边的人。如果i1 i2且heights[i1] hights[i2]则前面的任何人到看不到i2被i1所挡。淘汰i2后sta从栈底到栈顶降序。 如果当前元素高于栈顶元素则当前元素看得到栈顶。两者之间没有人高于等于栈顶之人否则栈顶之人早出栈了。 注意栈顶第一个高于等于当前人也可以看到只是看不到后面的人。 时间复杂度: o(n)每个人顶多出栈入栈一次。
代码
核心代码
class Solution {
public:vectorint canSeePersonsCount(vectorint heights) {m_c heights.size();vectorint vRet(m_c);stackint sta;for (int i m_c - 1; i 0; i--){while (sta.size() (sta.top() heights[i])){vRet[i];sta.pop();}vRet[i] !sta.empty();while (sta.size() (sta.top() heights[i])){sta.pop();}sta.emplace(heights[i]);}return vRet;}int m_c;
};测试用例
templateclass T
void Assert(const T t1, const T t2)
{assert(t1 t2);
}templateclass T
void Assert(const vectorT v1, const vectorT v2)
{if (v1.size() ! v2.size()){assert(false);return;}for (int i 0; i v1.size(); i){Assert(v1[i], v2[i]);}
}int main()
{vectorint heights;{Solution slu;heights { 10,6,8,5,11,9 };auto res slu.canSeePersonsCount(heights);Assert({ 3,1,2,1,1,0 }, res);}{Solution slu;heights { 5,1,2,3,10 };auto res slu.canSeePersonsCount(heights);Assert({ 4,1,1,1,0 }, res);}//CConsole::Out(res);
}2023年3月版二分查找
class Solution { public: vector canSeePersonsCount(vector heights) { m_c heights.size(); vector vRet(m_c); vector vDescHeight; for (int i m_c - 1; i 0; i–) { auto iNum std::upper_bound(vDescHeight.begin(), vDescHeight.end(), heights[i],std::greater()) - vDescHeight.begin(); if (iNum 0) { vRet[i] vDescHeight.size() - (iNum - 1); } else { vRet[i] vDescHeight.size(); } while (vDescHeight.size() (vDescHeight.back() heights[i])) { vDescHeight.pop_back(); } vDescHeight.push_back(heights[i]); } return vRet; } int m_c; }; 扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步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
我想对大家说的话闻缺陷则喜是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用C 实现。
