2023-09-09 16:32 阿里云_后端
关注
09.09 科大讯飞笔试第三题AC
这题是求一个数组的子数组，任意一个 ≥ 2的窗口中元素的均值都大于给定值，求这样一个子数组的最大长度。一趟遍历就可以完成。
考虑这样一个性质，因为窗口最小是2，所以子数组中，任意两个相邻元素的均值必须 ≥ m，因此我们可以用一个栈来记录这个最长子数组。
遇到本身＜m的元素，拉出来和栈顶元素求均值，≥ m就入栈（这里如果是连续好几个＜m的元素连在一块儿，就取他们中的最大值）
本身就 ≥ m的元素，直接入栈就行。
还需要注意处理栈内元素＞1的情况，比如给的测试用例【1，9，1】，相邻的两个元素均值都是 ≥ 5，但是三个连在一起就不是了，所以后面那个1不能入栈。
其实本质就是，只要保证连续两个元素的均值 ≥ m，而且连续三个元素的均值 ≥ m，就可以保证所有窗口的均值都 ≥ m，因为2和3能保证覆盖所有的奇偶数。
最后一趟扫描完，栈的大小就是结果。
考虑这样一个性质，因为窗口最小是2，所以子数组中，任意两个相邻元素的均值必须 ≥ m，因此我们可以用一个栈来记录这个最长子数组。
遇到本身＜m的元素，拉出来和栈顶元素求均值，≥ m就入栈（这里如果是连续好几个＜m的元素连在一块儿，就取他们中的最大值）
本身就 ≥ m的元素，直接入栈就行。
还需要注意处理栈内元素＞1的情况，比如给的测试用例【1，9，1】，相邻的两个元素均值都是 ≥ 5，但是三个连在一起就不是了，所以后面那个1不能入栈。
其实本质就是，只要保证连续两个元素的均值 ≥ m，而且连续三个元素的均值 ≥ m，就可以保证所有窗口的均值都 ≥ m，因为2和3能保证覆盖所有的奇偶数。
最后一趟扫描完，栈的大小就是结果。
全部评论
羊麻烦
南京大学 电子信息类
样例[9,2,6] 要求均值5 按照思路全部入栈了 但是2，6这个就不符合了
送花
回复
分享
雨中幻影
门头沟学院 计算机类
哥，有代码吗？
送花
回复
分享
滴滴
校招火热招聘中
官网直投
嘟嘟7噜 楼主
楼主 阿里云_后端
第一题用multiset直接暴力循环两遍，输出count == b的数字，第二题游程编码
送花
回复
分享
四月li
福州大学 计算机类
楼主思路写的，不知道对不对，可以参考一下
送花
回复
分享
相关推荐
点赞 评论 收藏
转发
03-28 23:30
四川大学 自动化类 点赞 评论 收藏
转发
投递阿里巴巴等公司10个岗位 > 2024校招宝典——软件... 点赞 评论 收藏
转发