Google 店面

owenqyzhang 发表于 2017-11-2 23:10
sort完以后就在index list里面找最大的差，而且保证大数在后面，参考 http://www.geeksforgeeks.org/maxi ...

类似max subarray sum?

owenqyzhang 发表于 2017-11-2 23:10
sort完以后就在index list里面找最大的差，而且保证大数在后面，参考 http://www.geeksforgeeks.org/maxi ...

但是在index list里找最大的差，还有保证A[j] = A[i] + 1,这部分怎么处理呢

补充内容 (2017-11-3 02:11):
A[j] = A[i] + 1

从后往前扫， 维护一个单调增的vector， 每次来的值大于最后一个元素就push_back, 搜索的时候就binarysearch， 这样可以吗？

我觉得可以把数字和index当做一个pair ,然后对pair按照数字的大小进行排序，（O(nlogn)）
然后对pairs从头开始扫描（O(n)），不断更新最小的index，然后对每对pair的index 减去最小的index，记录下最大的差值，应该就可以了

看到楼主说的follow up可以刀nlogn, 我在想是不是可以用multiset?
scan一遍，每次insert当前的数， 然后用lower_bound找到这个数在multiset中最靠前的位置，然后这个位置和multiset.begin()的差就是当前位置满足条件的最大差了
这个流程应该是nlogn的，但是似乎只能找到i<j的情况

另外14楼的说法应该是对的，我给想麻烦了

owenqyzhang 发表于 2017-11-2 07:12
比如A=[5, 2, 4, 5, 3, 1], 就返回(1, 4)

楼主，请问hashmap的做法是handle不了哪两种情况，看到你说j-i可以为负？ 那这样你给的这个例子是不是该返回（1，5）不是（1，4）？ 谢谢

owenqyzhang 发表于 2017-11-2 07:12
比如A=[5, 2, 4, 5, 3, 1], 就返回(1, 4)

楼主，请问hashmap的做法是handle不了哪两种情况，看到你说j-i可以为负？ 那这样你给的这个例子是不是该返回（1，5）不是（1，4）？ 谢谢

owenqyzhang 发表于 2017-11-2 07:12
比如A=[5, 2, 4, 5, 3, 1], 就返回(1, 4)

楼主，请问hashmap的做法是handle不了哪两种情况，看到你说j-i可以为负？ 那这样你给的这个例子是不是该返回（1，5）不是（1，4）？ 谢谢

张欣 发表于 2017-11-13 12:32
楼主，请问hashmap的做法是handle不了哪两种情况，看到你说j-i可以为负？ 那这样你给的这个例子是不是该 ...

hash map没有问题，做法类似2sum，(i, j)是有顺序的，(1, 5)是不对的，只有可能是(5, 1)，这样j-i就是-4