请问一道谷歌的onsite面经

给一个0和1的矩阵， 求出由1组成的rectangle的数量。
0,1,1
0,1,1
1,0,0
这个例子的话答案是：10个
因为1x1 矩阵有 5
1x2 矩阵有2
2x1 矩阵有2
2x2 矩阵有1

之前有道简单的小题，让你求出square的数量，这个答案就是6. 我用dp做的
除了brute force 应该有一些优化的做法。
注：把他看做histogram来解应该不是最优解，因为我是这么做的结果被挂了

求大神解释

Code在下面，Comment里写了思路，跟LC85是挺像的，就是Hist处理部分计算不一样。时间O(n^2)，空间O(n).

1. from typing import List
   
2. 
   
3. class Solution:
   
4.     def calc_matrix_rectangles(self, matrix: List[List[str]]) -> int:
   
5.         if not matrix or not matrix[0]:
   
6.             return 0
   
7.         ans = 0
   
8.         m, n = len(matrix), len(matrix[0])
   
9.         heights = [0] * n
   
10.         for i in range(m):
    
11.             for j in range(n):
    
12.                 if matrix[i][j] == 0:
    
13.                     heights[j] = 0
    
14.                 else:
    
15.                     heights[j] += 1
    
16.             ans += self.calc_hist_rectangles(heights)
    
17.         return ans
    
18. 
    
19. 
    
20.     def calc_hist_rectangles(self, heights: List[int]) -> int:
    
21.         # calculates the number of rectangles with base at bottom
    
22.         # e.g. heights = [2,0,3,2,1,2,4]
    
23.         #
    
24.         # the visualization below may be distorted when posted (but you get the idea)
    
25.         #             x
    
26.         #     x       x
    
27.         # x   x x   x x
    
28.         # x   x x x x x
    
29.         #
    
30.         # ans = 2 + 0 + 3 + (2 + 2) + (1 + 1 + 1) + (1 + 1 + 1 + 2) + (1 + 1 + 1 + 2 + 4)
    
31.         #       = 26
    
32. 
    
33.         ans = curr_sum = heights[0]
    
34.         l = 0
    
35. 
    
36.         for r in range(1, len(heights)):
    
37.             # starting a new round
    
38.             if heights[r] == 0:
    
39.                 curr_sum = 0
    
40.                 l = r + 1
    
41.                 continue
    
42. 
    
43.             # the rectangles extending to the left now have a lower height limit
    
44.             if heights[r] < heights[r-1]:
    
45.                 curr_sum = (r - l) * heights[r]
    
46. 
    
47.             # calculates the number of rectangles added when we reach at index r
    
48.             curr_sum += heights[r]
    
49.             ans += curr_sum
    
50. 
    
51.         return ans
    
52. 
    
53. if __name__ == '__main__':
    
54.     s = Solution()
    
55.     matrix = [[0,1,1],[0,1,1],[1,0,0]]
    
56.     print(s.calc_matrix_rectangles(matrix))
    

复制代码

Leetcode 1277 DP.

yuw485 发表于 2020-3-28 09:30
leetcode 85题原题。如果你的Histogram 算法是1维那就是最优算法。

补充内容 (2020-3-27 18:31):

更像是 1074. Number of Submatrices That Sum to Target

Histogram 算法具体指的是什么

leetcode 85题原题。如果你的Histogram 算法是1维那就是最优算法。

补充内容 (2020-3-27 18:31):
哦看错了不好意思不是一道题嘻嘻

感觉用Histogram的想法可以解，时间O(n^2), 空间O(n)

应该是histogram的做法，lz可能是面试时的算法计算错了，有重复统计

只要是不给最优解就挂吗

能说说你的DP具体怎么implement的吗？这题也不可能比O(n^2) time更优了吧? space 可能可以reduce成O(1).

clark.li86 发表于 2020-3-28 17:56
Leetcode 1277 DP.

好像可以把这道square题里的dp[i][i,j] = (width, top_continue, left_continue)拓展成 (width, height, top_continue, left_continue)然后用长宽的min做乘法？[/i]