落榜的DE编程打败了微软和亚麻的SDE！！！请为我鼓掌！

7月

脸书DE5 昂赛被拒，
亚麻BIE6被降级为5，我果断拒了亚麻

8月闭关刷题两周后，今天约了虾图两个小伙伴PK PYTHON算法，mock interview，一个是亚麻的SDE，另一个是微软的SDE。结果我把他们KO了，好开心。复盘如下：

You have a histogram. Try to find size of the biggest rectangle you can build out of the histogram bars in 15 minutes.

Input: List of all rectangles heights in histogram

Output: Area of the biggest rectangle

largest_histogram([5]) == 5
largest_histogram([5, 3]) == 6
largest_histogram([1, 1, 4, 1]) == 4
largest_histogram([1, 1, 3, 1]) == 4
largest_histogram([2, 1, 4, 5, 1, 3, 3]) == 8

corner case

histogram = [70,60,67,78,89,87,74,40,100,24,66,84,11,99,4,34,21,23,66,34,47,54,51,88,53,7,94,72,28,59,30,44,0,17,96,34,63,6,81,61,26,96,72,5,32,57,1,3,47,13,97,96,9,7,80,5,89,77,7,75,63,59,90,88,16,48,93,33,70,35,57,15,61,81,63,83,33,3,55,63,86,33,94,45,76,99,86,14,96,81,33,32,76,37,56,54,63,11,82,41,90,81,53,42,89,75,98,74,18,73,7,30,10,14,67,59,25,56,41,90,80,17,84,16,45,6,29,87,79,56,33,94,73,72,31,18,30,17,81,64,92,3,94,12,65,23,50,54,52,16,19,39,26,12,75,19,11,69,48,25,64,6,22,19,19,29,41,90,43,41,36,66,91,23,28,4,15,94,89,6,87,4,98,19,12,54,3,66,84,83,28,95,3,55,44,64,86,15,15,37,89,65,100,9,11,6,38,26,62,89,14,29,81,94,47,63,71,56,31,96,68,30,96,77,32,28,82,39,75,67,73,83,70,70,74,50,89,98,27,50,2,42,46,11,59,60,96,90,20,14,92,20,59,8,16,23,69,41,7,64,66,38,30,47,87,82,73,12,82,0,45,100,59,10,42,19,21,22,17,67,33,69,12,100,14,11,20,43,30,20,93,43,14,28,68,55,89,57,48,97,95,88,4,41,61,45,91,0,22,57,40,18,21,97,51,36,67,14,22,6,57,11,31,48,45,83,97,60,14,32,27,65,24,48,94,63,25,50,52,91,55,81,96,33,89,82,21,8,100,93,100,47,18,80,88,81,1,10,81,25,68,95,81,95,53,93,79,23,9,87,63,95,4,68,42,73,16,29,27,44,3,48,90,92,46,66,81,58,98,64,90,95,64,46,73,40,74,67,32,59,61,89,96,42,47,97,70,22,78,70,2,67,39,59,76,78,41,23,84,52,88,89,88,4,17,48,3,41,30,14,30,92,65,87,79,84,21,57,19,62,19,50,13,27,21,83,25,19,72,50,40,12,4,43,60,41,46,45,92,93,16,54,29,38,42,53,93,2,44,98,79,25,34,3,69,74,21,100,92,61,100,22,23,74,70,76,18,10,50,68,96,83,95,69,90,49,61,93,51,55,47,87,53,50,80,31,76,0,64,74,68,11,18,85,99,67,71,88,87,72,10,58,31,82,49,70,10,84,79,23,5,53,25,36,9,33,71,48,4,14,51,71,58,44,17,53,87,62,41,80,90,0,36,48,75,67,28,82,34,75,93,63,66,72,54,41,68,67,82,77,36,74,16,4,96,39,61,64,92,78,86,21,87,43,81,94,76,31,18,50,59,66,57,34,77,27,57,66,65,17,25,90,78,23,52,31,28,71,93,95,62,23,99,48,36,85,22,13,33,13,33,67,63,100,52,94,97,83,45,88,65,9,31,30,97,9,71,45,39,15,39,79,25,62,69,1,30,26,25,74,35,5,22,72,25,3,15,52,94,87,37,46,9,58,90,14,46,39,44,60,53,5,18,12,69,25,55,37,85,3,43,75,20,9,35,1,60,58,83,77,60,75,7,91,76,95,48,91,83,50,3,85,42,31,68,48,94,37,96,89,43,40,24,43,72,8,49,93,26,74,82,63,41,82,74,58,46,39,30,3,58,84,68,84,1,18,26,26,18,40,59,29,22,73,1,74,33,62,73,12,1,43,72,33,44,24,63,18,65,93,18,28,91,87,15,24,84,96,87,6,48,14,99,79,75,25,68,53,26,27,63,74,75,96,94,7,100,91,77,96,32,34,42,19,2,0,68,21,55,21,20,48,84,1,63,96,2,52,53,99,90,82,50,46,23,49,33,26,55,100,37,92,11,70,60,61,30,35,26,10,69,90,54,46,58,96,65,49,8,89,74,52,29,60,93,51,47,27,72,42,12,51,36,34,26,62,13,81,20,97,52,25,44,41,90,18,7,34,99,98,40,49,100,16,84,93,10,35,75,78,96,13,83,38,66,61,26,83,34,13,59,89,22,35,41,45,25,42,69,95,40,43,1,65,44,18,25,81,87,86,43,90,64,16,88,49,6,21,80,89,71,63,25,47,91,93,8,42,61,67,22,67,96,69,45,100,41,48,72,96,3,18,30,37,85,51,84,75,10,99,74,84,91,58,6,8,13,50,94,39,19,73,70,96,0,18,58,29,100,84,92,91,46,48,4,33,60,35,14,45,43,6,42,30,91,0,71,100,55,14,9,99,100,31,83,6,37,48,57]

这题不是lc84吗😂单调栈可以做到O(N)

oily 发表于 2020-08-17 23:59:06
lz你这回复把我看蒙了，原题没说需要空间O(1)或者空间最优吧，难道不是大部分时候先追求时间最优？要真提空间最优方案也得把时间最优的一起提了让面试官挑吧，上来就扯空间最优的话很多题你就枚举硬上空间已经

他就是自己先写了个比别人快一点的n^3暴力解贴出来炫耀，然后看回复在自己理解范围内憋出个n方解，但没想到这题最优是线性解，过了一天（也许）整明白了，然后硬撑扯线性解不一定就比n方好，因为需要耗空间，很典型因为基础不好许多概念都不理解，但还硬要自圆其说，就冲不懂装懂这一点面试也要把他筛掉，不然招进去写给你一堆极具破坏性的代码还想着花样给你merge进去

亚麻SDE的解法（Corner Case 测试：用时8秒钟！！！）

1. def largest_histogram(histogram):
   
2.     result, width = 0, len(histogram) + 1
   
3.     for i in range(1, width):
   
4.         for j in range(width - i):
   
5.             rect = i * min(histogram[j:][:i])
   
6.             result = max(result, rect)
   
7.     return result

复制代码

微软SDE的解法（Corner Case 测试：用时6秒钟！！！）

1. def largest_histogram(histogram):
   
2.     lgth = len(histogram)
   
3.     ans = max(histogram)
   
4.     for i in range(2,lgth+1):
   
5.         s = [min(histogram[k:k+i])*i for k in range(lgth-i+1)]
   
6.         s.append(ans)
   
7.         ans = max(s)
   
8.     return ans

复制代码

我的解法（Corner Case 测试：用时1秒钟！！！）

1. def largest_histogram(histogram):
   
2.     result = 0
   
3.     for i in range(len(histogram)):
   
4.         w = 0
   
5.         for j in range(len(histogram[i:])):
   
6.             if histogram[i] <= histogram[i:][j]:
   
7.                 w += 1
   
8.             else: break
   
9.         for k in reversed(range(len(histogram[:i]))):
   
10.             if histogram[i] <= histogram[:i][k]:
    
11.                 w += 1
    
12.             else: break  
    
13.         result = max(result,histogram[i]*w)
    
14.     return result

复制代码

[/i][/i][/i]

楼主你把那个corner case的定义后面再加一行：
histogram_100 = histogram * 100

那么 largest_histogram(histogram_100) 大概会一个小时都跑不完.. 因为这三个方法都是 n^3 时间（如果Python像R一样支持Copy-on-write的话，这三个方法则可以到O(n^2)时间，可惜并不）

而这道题的目标一般是O(N)，换句话说 histogram_100 至少要做到100毫秒以内.. 最优解要涉及一些non-trival的子数组上的性质，属于组合优化类问题，用data analytics一些常规operator（比如array slicing、list comprehension）来表达然后还要比性能的话就比较尴尬

牛了，拒了亚麻竟然

啥意思啊……

把lc的最优的答案贴在这里，O(n)，仅供大家参考。 至于楼主的三种解法，我个人认为都是O(n^2)，如果说得不对请大家指正。

1. public class Solution {
   
2.     public int largestRectangleArea(int[] heights) {
   
3.         Stack < Integer > stack = new Stack < > ();
   
4.         stack.push(-1);
   
5.         int maxarea = 0;
   
6.         for (int i = 0; i < heights.length; ++i) {
   
7.             while (stack.peek() != -1 && heights[stack.peek()] >= heights[i])
   
8.                 maxarea = Math.max(maxarea, heights[stack.pop()] * (i - stack.peek() - 1));
   
9.             stack.push(i);
   
10.         }
    
11.         while (stack.peek() != -1)
    
12.             maxarea = Math.max(maxarea, heights[stack.pop()] * (heights.length - stack.peek() -1));
    
13.         return maxarea;
    
14.     }
    
15. }

复制代码

[/i]
看到有人说是O(n^3)，我对python内部原理不熟悉，也可能数组切片的操作也要花n？那就变成O(n^3)了。不过直觉上个人感觉python不会那么蠢。。。

jerry4013 发表于 2020-8-17 21:53
把lc的最优的答案贴在这里，O(n)，仅供大家参考。 至于楼主的三种解法，我个人认为都是O(n^2)，如果说得不 ...

对的， python里数组切片是要花时间的，复杂度取决于你切多少，假设取K，时间复杂度就是O(K)。

优化方法也有，就是传起始的index而不是整个切片。

如果还有其他优化方法，欢迎分享