Google virtual onsite

请问题主的BQ问的是什么呀？另外能不能提供一下timeline作为参考，谢谢题主呀！！祝顺利match 到纽约

Ljw921111g 发表于 2020-3-27 01:06
是O(N^2)，每行做两件事请，第一个调用第一问的方法，O(n), 第二个算柱状图的面积，O(n), 一共n行，所以O ...

谢谢楼主回复
求柱状图面积的部分, 可以再分享一下思路吗? 或者再给个范例吗?

我原本以为, 柱状图是求到index i 的部分
0~index i 的最大柱状图O(N)
每个i 需要做一次? 不过我应该是哪边没有想清楚了.

谢谢楼主 !!

reliveinfire 发表于 2020-3-27 11:33
谢谢楼主回复
求柱状图面积的部分, 可以再分享一下思路吗? 或者再给个范例吗?

同求怎么用o（n） 求柱状图的面积呀。
lz 说的单调栈是单调递增还是递减？

1009 发表于 2020-3-27 11:38
同求怎么用o（n） 求柱状图的面积呀。
lz 说的单调栈是单调递增还是递减？

同问！我不太懂为什么求面积就能知道能多加几个submartrix呀

有用的信息谢谢

楼主第一题有一个问题比如这个例子：
1，1，1，0
0，1，0，0
0，0，0，0
0，0，0，0
当第四行的时候 向上看0个数的数组为[2,1,2,3], 每个index能生成的柱状图的最大面积对应为[2,2,3,4]. 然而实际上因该增加的submatrix应该为[+2,+2,+4,+7]，所以有疑问，这里应该怎么用monotone stack求呢？
多谢！！

楼主积分能设置低一些吗。。。

匿名者 发表于 2020-3-27 14:55
楼主第一题有一个问题比如这个例子：
1，1，1，0
0，1，0，0

不好意思，我觉得那个方法是有点问题的，按照我的方法，你的例子，每个index的最大柱状面积是[2, 4, 4, 3]，不过也是有问题的。sorry

llcourage123 发表于 2020-3-26 09:17
楼主，你能详细解释下第四题题干么，我的理解是，如果一个长度大于1的substring出现过两次，那么就输出这个 ...

就是aaabccc，就是输出a的range[0,2], c的range[4,6]

google 这么狠 4道hard题目