[求助]大米请教几道最近亚麻OA题思路

话说这积分限制要怎么取掉，或者我能自己改低点让更多人看到吗。设置个10，20之类的
准备做OA了翻了下note，才发现有几道没头绪的题（非暴力解）
1. nums=[1,5,4], limit = 3。 要求：对每一个subarray中 max - min <= limit，求subarray个数。想用两个mono queue 一个记大， 一个记小，找到不符合的subarray的个数。但是这样好像无法保证每

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

个customer被多少retailer覆盖（即customer的xy坐标在多少retailer的xy坐标内或者边缘上（<= 关系） 自己太笨，只能想到n^2。 retailer和customer的y都不超过100，不知道这里是不是可以做文章。

先谢谢了。祝大家面试顺利。

希望有大牛能看到援助下啊

第一题mono queue + sliding window可以达到O(n)解
跟这题很类似：https://leetcode.com/problems/lo ... -or-equal-to-limit/

GrandMaestro 发表于 2022-3-2 17:40
第一题mono queue + sliding window可以达到O(n)解
跟这题很类似：https://leetcode.com/problems/longest ...

谢谢，加米了。但那道利口只需要关注最大区间，并不能考虑到每个subarray吧？

rekoko555 发表于 2022-3-2 20:56
谢谢，加米了。但那道利口只需要关注最大区间，并不能考虑到每个subarray吧？

对 稍微有点不同，但是也差不多。
那题里面我们其实是在以看每个element作为右边，然后向左延申的最长的区间。在每个最长的区间里面，我们要计算一下所有以右边结尾的区间的个数（满足条件的区间里面每一个小的区间也都满足条件）。他们的和就是全部的unique subarray了

[2, 4, 7, 2] => [2], [7, 2], [4, 7, 2], [2, 4, 7, 2] 刚好和长度一样。所以把更新max的地方改成加上right-left+1就可以了

GrandMaestro 发表于 2022-3-2 21:39
对 稍微有点不同，但是也差不多。
那题里面我们其实是在以看每个element作为右边，然后向左延申的最长的 ...

对哈，满足条件的区间内子区间也满足。facepalm
谢谢指导！
可惜一次只能加一分，不然我把今天的全给你 哈哈

retailer那个不是挺简单。就按照retailer y 坐标map reduce一下，map <int, multiset<int>>这样子存，然后multiset里面存x坐标。每回来一个request,就先在map里面upper_bound一下，然后从那个iterator开始遍历，找到一个key，就在multiset里面再upper bound一下，符合条件的数量就这样计算auto itr = x->second.upper_bound(request.x), int num = distance(itr, x->second.end())
map里头按照y坐标搜是log 100，然后每个x坐标因为已经是sorted,所以再upper bound也是logrithm. 最后应该就挺快的。