亚麻VO战三哥

楼主因为已经接了其他家的offer了，所以就没怎么准备A家。这次碰到了两个三哥，上来还是一堆BQ，我即兴发挥了一下。然后开始coding部分。
这里建议大家要求面试官直接把题目贴上去。三哥一开始跟我口述题目（口音比较重），花了十分钟才讲清楚（因为最后他还是把题目粘贴过来了，我就不是很懂，您一开始直接贴题目不就行了吗）。

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

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

注：这题最优解应该是时间复杂度O(n)，空间复杂度O(1)，大家自行脑补吧



补充内容 (2019-2-21 05:14):
推荐 yrccheer的方法：从后往前维护最小值，解释见下面帖子。
lz方法：记录从0开始的连续点亮的长度k，用原来数组的正负记录是否点亮；如果当前值等于k，那么result+1并且更新k直到下一个没被点亮的灯。

是从后往前遍历一遍？维持一个当前点燃序号的最小值，如果大于这个最小值就不能点燃，小于就可以点燃？

从左往右扫描，维护一个单调递增栈，最后栈里的元素个数就是会闪的次数
例子5 1 3 2 4，栈最后是1 2 4，闪3次

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

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

O(n)是反过来从最后一个灯开始走回来的最长递减数列吗?

otaku0628 发表于 2019-2-21 03:33
O(n)是反过来从最后一个灯开始走回来的最长递减数列吗?

[2, 3, 1, 4]  只会亮两次。而且求最长递减数列的空间复杂度达不到O(1)

yrccheer 发表于 2019-2-21 03:58
是从后往前遍历一遍？维持一个当前点燃序号的最小值，如果大于这个最小值就不能点燃，小于就可以点燃？

试一下给的例子

楼主能分享一下想法吗，谢谢

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

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

yrccheer 发表于 2019-2-21 04:08
最后一个元素肯定是true，初始设成Integer.MAX_VALUE，当2的时候，min=4，22所以是false，1的时候，min=2 ...

楼主给了个例子 2， 3， 4， 1，貌似这个case过不了？

simonwux1 发表于 2019-2-21 04:29
楼主给了个例子 2， 3， 4， 1，貌似这个case过不了？

lz写的是 2 3 1 4吧？这样的话就是1 和 4亮，2和3不能亮，感觉是可以的？

维护两个变量，一个counter是目前左边点亮的灯泡数量，另一个是当前见过的灯泡里没点亮的最小值；如果我们到一个灯泡，发现对应值正好是counter + 1 ，那么它闪烁，然后counter++；如果不闪烁，更新不闪烁的灯泡最小值；另外每次循环的开始，如果最小值刚好是counter + 1，那么更新counter++。
不知道这个方法行不行，还有2小时面试，求人品