关注
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
int findleftmaxnum(vector<int> &nums,int l,int r)
{
int maxnum = nums[l];
for(int i=l;i<r;i++)
{
maxnum = maxnum<nums[i]?nums[i]:maxnum;
}
return maxnum;
}
int findrightindex(vector<int> &nums,int maxnum, int l)
{
int index = l;
for(int i = nums.size()-1;i>l;i--)
{
if(nums[i]<maxnum)
return i;
}
return l;
}
//10
//69079936 236011312 77957850 653604087 443890802 277126428 755625552 768751840 993860213 882053548
int main()
{
int n = 0;
cin>>n;
vector<int > nums,numa;
unordered_map<int, int> mp;
for(int i=0;i<n;i++)
{
int temp = 0;
cin>>temp;
nums.push_back(temp);
numa.push_back(temp);
mp[temp] = i;
}
sort(nums.begin(),nums.end());//排序用于定位当前区间的最小值
int count = 0;
for(int i=0;i<nums.size();i++)
{
int temp = nums[i];
int index = mp[temp];
int maxnum = findleftmaxnum(numa,i,index);//找到当前区间的最小值左侧的最大值元素的值
int right =findrightindex(numa,maxnum,index);//从当前区间的最右侧开始 找到第一个小于上一步找到的最大值的值
i = right;//划分区间
count++;
}
cout<<count<<endl;
return 1;
}
//12 18 14 11 15 6 7 14 20 6 19 20 23 22
//2 1 3 2 4 3 5 3 6 5 7 6 7 答题的时候A了18,后来发现判断条件的时候多了个等号,去掉后感觉能提高不少,思路类似快排,只不过每次先找当前区间的最小值,然后找最小值左侧的最大值,判断这个最小值和最大值确定的区间能覆盖的范围,该范围就是一个满足要求的区间,然后再进行后面区间的partition。 C++代码。
查看原帖
点赞 评论
相关推荐
不愿透露姓名的神秘牛友
04-24 12:10
点赞 评论 收藏
转发
点赞 评论 收藏
转发
牛客热帖
- 1... 想来字节技术实习,看我这篇就够了!——保姆级面经大放送1.9W
- 2... 外卖员面试经验1.6W
- 3... 25届第一份实习怎么找?1.4W
- 4... 0实习经验上岸字节,分享一下过程经验1.3W
- 5... 【奖】休息放松or学习提升,五一假期和牛牛一起“充充电”🔋1.1W
- 6... 【0429快问快答】99%牛油的疑惑解答(更新至38个问题1.0W
- 7... 准备去参加自己的婚礼8884
- 8... 美团后端日常实习一二面(已oc)8573
- 9... 【💰有奖征集】非技术岗位笔面经邀你来分享!攒人品时间到!6121
- 10... 阿里国际 笔试 04295154
正在热议
# 牛友的五一计划 #
17813次浏览 373人参与
# 晒一晒我的offer #
2827890次浏览 49952人参与
# 牛客帮帮团来啦!有问必答 #
399390次浏览 7823人参与
# 无实习如何秋招上岸 #
173128次浏览 2725人参与
# 如何看待offer收割机的行为 #
194434次浏览 2989人参与
# 如何一边实习一边秋招 #
201675次浏览 4002人参与
# 华为求职进展汇总 #
442448次浏览 4443人参与
# 春招别灰心,我们一人来一句鼓励 #
21461次浏览 311人参与
# 产品实习,你更倾向大公司or小公司 #
31254次浏览 491人参与
# 非技术岗薪资爆料 #
8675次浏览 182人参与
# 硬件人的春招flag #
14562次浏览 199人参与
# 女生做医疗销售有前景吗 #
3880次浏览 49人参与
# 字节跳动工作体验 #
53727次浏览 1561人参与
# 聊聊这家公司值得去吗 #
63493次浏览 1261人参与
# 第一次面试 #
17707次浏览 272人参与
# 在国企工作的人,躺平了吗? #
72967次浏览 881人参与
# 机械人,你的秋招第一份简历被谁挂了 #
27004次浏览 491人参与
# 来聊聊机械薪资天花板是哪家 #
22833次浏览 180人参与
# 你更愿意参加线上面试还是线下面试? #
6970次浏览 95人参与
# 如何KTV领导 #
7546次浏览 73人参与