谷歌实习电面

oneexy 发表于 2018-2-13 04:45
O(nlgn)解法

谢谢你

但是我突然想到用stack 可以O(n)

从前往后
8 3 3 5 9 4
如果递减 压进栈 idx , 括号里表示对应数值
0（8） 1（ 3） 2（ 3)
遇到 3(5) 大于栈顶， 就一直出栈并且 更新这些idx 上的值

并且把 3（5） 压进
0（8） 3（5）
这样应该是O(n)的

还是很谢谢你的 回答！！

greynut 发表于 2018-2-13 05:50
谢谢你

但是我突然想到用stack 可以O(n)

8 3 9 5 9 4呢，你怎么办

oneexy 发表于 2018-2-13 06:16
8 3 9 5 9 4呢，你怎么办

[ 0 (8)]   [0 0 0 0 0 0]

[ 0(8) 1(3)]  [0 0 0 0 0 0]

[2(9) ]  [2,1,0 0 0 0]

[2(9) 3(5)]  [2,1,0 0 0 0]

[2(9) 4(9)]  [2,1,0,1,0,0]

[2(9),4(9), 5(4)] [2,1,0,1,0,0]

def find(nums):
    stack = []
    ans = [0] * len(nums)
    for i in range(len(nums)):
        if stack == [] or nums[i] <= nums[stack[-1]]:
            stack.append(i)
        else:
            while len(stack) > 0 and nums[i] > nums[stack[-1]]:
                idx = stack.pop(-1)
                ans[idx] = i - idx
            stack.append(i)
    return ans
哪里错了吗
请指教

greynut 发表于 2018-2-13 06:58
[ 0 (8)]   [0 0 0 0 0 0]

[ 0(8) 1(3)]  [0 0 0 0 0 0]

我想错了，的确是O(n)

类似lc315 用BST可给出O(n)解

从后往前遍力, stack存最大的

4 进stack, 9 , stack pop , 9 进去, 因为9比4大, 然后5, 直接进stack, 因为比9小, 然后3直接进去, 然后又是3, pop一个3, 然后进去, 然后8, pop(3,5), 然后进去

每次进去前和stack顶端那个算距离就行了

时间复杂度, 最快o(n), 最慢o(n^2), 因为9,1,2,3,4,5,6,7,8, 这种case, 读到9时必须要pop所有

gameboyying 发表于 2018-3-23 05:36
从后往前遍力, stack存最大的

4 进stack, 9 , stack pop , 9 进去, 因为9比4大, 然后5, 直接进stack, 因 ...

复杂度严格O(n)，即便是你给的case里也是O(n)
证明思路：
首先，代码里对于栈是没有遍历操作的，所谓的遍历栈就是在弹栈，栈的规模越来越小【不像vector，遍历过之后vector的元素个数可以不变】；一个数字至多入栈+出栈各一次，故复杂度O(2*n) = O(n)

没看懂第二题，input 是 8, 3, 3, 5, 9, 4.
output 怎么会是 4, 2, 1, 1, 0, 0呢？
能解释下吗？

alanlxl 发表于 2018-3-23 16:08
复杂度严格O(n)，即便是你给的case里也是O(n)
证明思路：
首先，代码里对于栈是没有遍历操作的，所谓的 ...

对的，每个element都是进一次出一次，2n => O(n).

請問第一題有出現在LeetCode上嗎