狗店面

唉，非常简单的题，可惜答的不是很好。


给一个int [] errRate, 一个阈值， 一个时间t

errRate数组表示在每一个时间当前的error Rate.
如果有一个包含时间t 的sub-interval 满足：min of interval * size of interval >

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

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

rn true.
if er[i] == 0, keep going until not, reset the size and curMin.


祝大家好运，也祝我好运。

单调栈。。。。
只要后面比栈顶大/一样就push，不然就pop
中间有t才开始计算
h = s.pop()
w = i - s[-1] - 1
ans = min(ans, h*w)
时间空间都是O(n)
followup就不用判断中间有t

jtqv84 发表于 2021-7-1 15:35
我怎么感觉第一问也是O(N^2)呀？t左边有t个起始点，t右边有N-t个终止点

第一问应该是O(N)就行了。因为只需要从t出发往左右两边走，最坏情况是整个数组遍历完

84 monostack O(n)可以做

我怎么感觉第一问也是O(N^2)呀？t左边有t个起始点，t右边有N-t个终止点

LZ min of interval 是什么意思啊， followup可以sort 序列吗

anna-1080 发表于 2021-7-1 15:55
LZ min of interval 是什么意思啊， followup可以sort 序列吗

就是这个区间里面的最小值。
我的理解是不能sort，因为每个元素之间的相对位置是有意义的，sort的话会丢失位置信息。

lynnnaive16 发表于 2021-7-2 13:37
84 monostack O(n)可以做

看了一下这个题确实抽象出来跟follow up 挺像的，感谢分享！

ja0b 发表于 2021-7-3 08:32
第一问应该是O(N)就行了。因为只需要从t出发往左右两边走，最坏情况是整个数组遍历完

这样只能cover起点或者终点是t的情况？怎么加上横跨两边的case？

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

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