牛客 奇怪的排序问题(单调栈/遍历)
发布日期:2021-07-01 03:34:58
浏览次数:2
分类:技术文章
本文共 1315 字,大约阅读时间需要 4 分钟。
文章目录
1. 题目
链接:
来源:牛客网操场上有n个人排成一队,这n个人身高互不相同,可将他们的身高视为一个1到n的排列。
这时需要把队伍变成升序,也就是从矮到高排序。每次可以选择一个人,让这个人和在他身后的人比高矮,如果比对方高,则交换位置并继续下一次比较,直到比对方矮或者已经在队尾。
现在给出数n和一个1到n的排列,求最少的选择次数,使队伍变为升序。
示例1输入4,[4,1,2,3]返回值1备注:n<=10^6数据包含一个整数n和一个含有n个元素的数组,表示从队头到队尾的人的身高。输出一个整数表示答案。
2. 解题
- 单调栈,当栈顶的身高 比 当前的大 ,需要移动一次
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * @param n int整型 * @param a int整型vector * @return int整型 */ int wwork(int n, vector & a) { // write code here int ans = 0; stack s; for(int i = 0; i < n; i++) { while(!s.empty() && s.top() > a[i]) { ans++; s.pop(); } s.push(a[i]); } return ans; }};
- 直接反向遍历,当前身高比后面最小的大,就需要移动一次
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * @param n int整型 * @param a int整型vector * @return int整型 */ int wwork(int n, vector & a) { // write code here int ans = 0, MIN = INT_MAX; for(int i = n-1; i >= 0; --i) { if(a[i] > MIN) ans++; MIN = min(MIN, a[i]); } return ans; }};
我的CSDN
长按或扫码关注我的公众号(Michael阿明),一起加油、一起学习进步!
转载地址:https://michael.blog.csdn.net/article/details/111397118 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
哈哈,博客排版真的漂亮呢~
[***.90.31.176]2024年04月18日 03时07分21秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
代码整洁之道-编写 Pythonic 代码
2019-05-01
树莓派程序开机自启动
2019-05-01
连锁门店无线通信方案
2019-05-01
配置Lotus Domino集群视频详解
2019-05-01
Linux软件万花筒
2019-05-01
全球开源软件发展趋势分析
2019-05-01
Linux常用的安全工具
2019-05-01
python 多进程之进程池的操作
2019-05-01
flask整理之 flask程序中的debug模式
2019-05-01
比特币,父母这一辈能接受吗?
2019-05-01
为什么要反对比特币,这不代表是空气币
2019-05-01
SnapEx的新感觉,对新手很友好
2019-05-01
首个聚合器怎么产生的,并运用领域在什么
2019-05-01
区块链技术应用,最先医疗行业
2019-05-01
新币上市旧币会降价吗
2019-05-01
当博士进入币圈会怎么样
2019-05-01
PHP之 使用PHPMailer插件实现邮件发送功能
2019-05-01
《增长黑客》(肖恩·艾利斯)学习笔记——第二部分 实战
2019-05-01
python使用HTMLTestRunner查看运行函数
2019-05-01
python的ImportError
2019-05-01