脸家面经

第一题是二分长度+两个单调队列找min和max吧。从头到尾O(n)校验，当窗口大小为mid且max-min=mid-1就找到了。然后继续二分长度，直到退出。

补充内容 (2021-09-24 08:35 +08:00):
所以是O(nlogn)

xqfq 发表于 2021-9-23 20:32
在你楼下，谢谢你的o(n^2)滑动窗口解法，我看看

谢谢分享哈。
比如[2,1,3,4,0,1,2,9]，第一次mid对应是4然后第一个窗口找到了是[2,1,3,4]，请问你下一步怎么二分能保证最后找到的最长的是[3,4,0,1,2]呢

写了个nlogn 的代码。

1. def findMaxSubarray(nums):
   
2.    
   
3.     def slidingMin (k):
   
4.         dq = deque([])
   
5.         res = []
   
6.         for i, num in enumerate(nums):
   
7.             while dq and nums[dq[-1]] >= num:
   
8.                 dq.pop()
   
9.             dq.append (i)
   
10.             while dq and dq[0] <= i - k:
    
11.                 dq.popleft()
    
12.             if i >= k - 1:
    
13.                 res.append (nums[dq[0]])
    
14.         return res
    
15.    
    
16.     def slidingMax (k):
    
17.         dq = deque([])
    
18.         res = []
    
19.         for i, num in enumerate(nums):
    
20.             while dq and nums[dq[-1]] <= num:
    
21.                 dq.pop()
    
22.             dq.append(i)
    
23.             while dq and dq[0] <= i - k:
    
24.                 dq.popleft()
    
25.             if i >= k - 1:
    
26.                 res.append(nums[dq[0]])
    
27.         return res
    
28.    
    
29.     def is_valid (k):
    
30.         k_window_min = slidingMin (k)
    
31.         k_window_max = slidingMax (k)
    
32.         for k_min, k_max in zip(k_window_min, k_window_max):
    
33.             if k_max - k_min + 1 == k:
    
34.                 return True
    
35.         return False
    
36.    
    
37.      # binary search over the size of subarray
    
38.     lo, hi = 1, len(nums)
    
39.     while lo < hi:
    
40.         # since we are moving [lo] pointer, take [mid] to be (hi + lo + 1) // 2 to avoid infinite loop
    
41.         mid = lo + (hi - lo + 1) // 2
    
42.         if is_valid(mid):
    
43.             lo = mid
    
44.         else:
    
45.             hi = mid - 1
    
46.     return lo
    
47.             
    
48. 
    
49. print(findMaxSubarray([2,11,3,4,0,1,2,9])) #5
    
50. print(findMaxSubarray([2,8,1,2,3,9,4])) #3
    
51. print(findMaxSubarray([1,3,2,5,4,6,7,8,9])) #9
    
52. print(findMaxSubarray([2,1,1,2,3])) #3
    
53. print(findMaxSubarray([1,2,1,4])) #2
    
54. print(findMaxSubarray([1,2,3,4])) #4
    
55. print(findMaxSubarray([1,1,1,1])) #1

复制代码

谢谢楼主分享

匿名者 发表于 2021-9-24 08:05
写了个nlogn 的代码。

是不对的，好像不能够二分。
试试这个例子 print(findMaxSubarray([11,2,3,4,0,5,1,9])) 你的program 会print 3， 但是答案是6

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

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

Znedison 发表于 2021-09-24 17:45:35
好像是不对的，如果数组中存在一个长度为6的subarray，但是不能保证长度为4的subarray一定存在，这时候二分的upper bound会回收到4 永远到不了5

有道理 没考虑到..

匿名者 发表于 2021-9-24 07:05
写了个nlogn 的代码。

多谢大家指正。二分法是不行的。因为我们并不能保证 如果长度m不存在，那么n >= m也不存在。比如这个例子[11,2,3,4,0,5,1,9]，长度4不行，但是6可以。二分的话，会输出错误结果。

谢谢分享！

Znedison 发表于 2021-9-24 17:45
好像是不对的，如果数组中存在一个长度为6的subarray，但是不能保证长度为4的subarr ...

好tricky，要是面试就挂了TVT