kylinnnnn
2022-09-27 09:38 浙江大学 C++
关注
优化一下，O(n)算法：
流程一样，数据结构上不用堆来找最小值了，因为我们每次找最小值是向右侧一直找到数组末尾，那只需要用一个数组记录一下每个位置上后缀数组的最小值就行。
算法流程开始前，先从前向后遍历得到前缀最大值数组，再从后向前遍历得到后缀最小值数组，顺便用hashtable记录每个值在数组中的下标（重复的时候记录最右边那个）
每次找数组最小值的时候，直接去找后缀最小值，如果它比之前已经归入非降数组部分的max还要小，那么它肯定由于之前的操作递增到了max非降，那最小值就是 max非降，否则就是后缀最小值里记录的那个值。后面操作完成，将左侧数组归入非降数组部分的时候，还要遍历左侧数组更新一下hashtable。
整个过程遍历数组3次，O(n)
查看原帖
点赞 评论
相关推荐
游卡公司福利 133人发布 点赞 评论 收藏
分享
在等offer的比尔很洒脱：我也是在实习，项目先不说，感觉有点点小熟悉，但是我有点疑问，这第一个实习，公司真的让实习生去部署搭建和引入mq之类的吗，是不是有点过于信任了,我实习过的两个公司都是人家正式早搭好了，根本摸不到部署搭建的
点赞 评论 收藏
分享
SomeLucky：五段实习 哈哈 不就相当于大一开始就去实习才够五段啊 牛掰
点赞 评论 收藏
分享
投递科大讯飞等公司10个岗位 > 点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 笔试 #
2008788次浏览 22889人参与
# 金融银行面经 #
60238次浏览 479人参与
# 腾讯音乐26届实习 #
115285次浏览 849人参与
# 牛友故事会 #
161591次浏览 2599人参与
# 技术岗笔试题求解 #
18996次浏览 278人参与
# 两会劳动法放大招 #
21642次浏览 427人参与
# 元戎现在香不香 #
64019次浏览 523人参与
# 夸一夸2024年的自己 #
21675次浏览 188人参与
# 双非应该如何逆袭？ #
20322次浏览 746人参与
# 互联网回暖，腾讯要招5000人！ #
5555次浏览 80人参与
# 网易求职进展汇总 #
71684次浏览 551人参与
# 我的省钱小妙招 #
4491次浏览 145人参与
# 你投递的公司有几家约面了？ #
55098次浏览 399人参与
# 如果中了500万，你会离职吗？ #
57590次浏览 417人参与
# 蔚来开了，制造业的牛友投递了吗？ #
21786次浏览 188人参与
# 你怎么评价今年的春招？ #
85149次浏览 1111人参与
# 面试体验感最好的是哪家？ #
133267次浏览 1453人参与
# 实习/项目/竞赛奖项，哪个对找工作更重要？ #
48577次浏览 640人参与
# 打工人的精神状态 #
25600次浏览 436人参与
# Tplink求职进展汇总 #
106399次浏览 592人参与
# 我和xx公司的爱恨情仇 #
35786次浏览 301人参与
# 大城市找工作会更容易吗 #
6563次浏览 34人参与