狗家电面

zzy1993 发表于 2018-1-18 22:47
我有个思路。找到的这个index，一定满足 max(A[0 to index] ) < min(A),所以开一个int[] left保存从左往右 ...

思路对了，但是这是O(n)空间的，原因是你没有利用数组数都是1～n的条件。
如果能利用这个条件，你这个就可以做到O(1)空间，一趟遍历。具体code可参考我第一页的回帖。

nicemayi 发表于 2018-1-18 18:29
先从后往前遍历第一次，维护一个最小堆；再从前往后遍历第二次，维护一个最大堆；在第二次遍历的时候，当最 ...

思路对了，但是实现。。。我知道你想到了LC的某题，但这里套错了。。
先参考zzy1993 的回帖，把实现进化成他的那样（就是把你的两个堆变成了数组，性能是 2趟遍历，O(n) 空间），再参考我第一页回帖，继续进化到 一趟遍历，O(1)空间。

幕云飞 发表于 2018-1-4 17:25
为什么我觉得第二个case解是2呢？
题意说最小index，而且没规定生序或者降序

哈，你这个想法有意思，应该是面试官没说清，或者lz忘说了。不规定升序降序的话，确实你是对的。

fentoyal 发表于 2018-1-20 04:08
思路对了，但是实现。。。我知道你想到了LC的某题，但这里套错了。。
先参考zzy1993 的回帖，把实现进化 ...

大小堆用在这里没啥大问题吧 不过确实o(n)更好 我确实第一反应就是去套题了lol

nicemayi 发表于 2018-1-20 14:07
大小堆用在这里没啥大问题吧 不过确实o(n)更好 我确实第一反应就是去套题了lol

如果是面试题来考虑，算法复杂度过高是大问题。。。
咱们学一大堆什么堆树二分，不就为了提高那么一丢丢效率么，不考虑复杂度的话，很多LC hard都可以降维成medium甚至easy。

fentoyal 发表于 2018-1-21 05:45
如果是面试题来考虑，算法复杂度过高是大问题。。。
咱们学一大堆什么堆树二分，不就为了提高那么一丢丢 ...

同意你的解法 这道题我overkill了

Mark, mark. marrk,