骨骼蠡口分类整理追加单调队列

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

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

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

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

这才是值得加分的精华帖子

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

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

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

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

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

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

yangzhit 发表于 2020-7-12 16:55
谢谢，不确定。如果有相应解法或链接，麻烦贴出来

1. class Solution:
   
2.     def numSubmat(self, mat) -> int:
   
3.         '''
   
4.             1 0 1
   
5.             1 1 0
   
6.             1 1 0
   
7. 
   
8.               ↓ use prefix sum by column
   
9. 
   
10.             1 0 1
    
11.             2 1 0
    
12.             3 2 0
    
13. 
    
14.         calculate the prefix sum, like:
    
15.         
    
16.                 h: [2 2 4 3 1]
    
17.             index:  0 1 2 3 4
    
18.         
    
19.         
    
20.         stack = [(-1, 0)]
    
21.         stack.append (i, h[i]) when it is increasing.
    
22.         Once you find h[3] = 3 which is not increasing,
    
23.             you pop items from stack (i, h[i]),
    
24.             until the item on the top of the stack has a lower height
    
25.         
    
26.         this property means that:
    
27.             
    
28.             
    
29.         # of rectangles created by the popped column =
    
30.             [cur(i) - popped(i)]
    
31.             * [popped(i) - stack[-1][0]]   
    
32.             # 左边包含 popped column 的 能组成正方形的长度 * 右边... （左边和右边，包含 popped column 的 所有组合）
    
33.             * h[popped(i)]
    
34.             
    
35.         '''
    
36.         for row in mat:
    
37.             row.append(0)  
    
38.         
    
39.         col = len(mat[0])
    
40.         res = 0
    
41.         h = [0 for _ in range(col)]
    
42.         
    
43.         for row in mat:
    
44.             stack = [(-1, 0)]
    
45.             
    
46.             for i in range(col):
    
47.                
    
48.                 h[i] = h[i] + 1 if row[i] == 1 else 0 # calculate the height  
    
49.                
    
50.                 while stack and len(stack) > 1 and h[stack[-1][0]] > h[i]: #  and len(stack) > 1 是因为有可能 h[stack[-1][0]] 是 h[-1] 就错了
    
51.                     popped_i, popped_h = stack.pop()
    
52.                     res += (i - popped_i) * (popped_i - stack[-1][0]) * popped_h
    
53.                
    
54.                 stack.append((i, h[i]))
    
55.             
    
56.         return res         
    
57.         
    
58.         
    
59.         
    
60.         
    
61.     def numSubmat___(self, mat) -> int:
    
62.         '''
    
63.             1 0 1
    
64.             1 1 0
    
65.             1 1 0
    
66. 
    
67.               ↓ use prefix sum by column
    
68. 
    
69.             1 0 1
    
70.             2 1 0
    
71.             3 2 0
    
72. 
    
73.         calculate the prefix sum, like:
    
74.         
    
75.                 h: [2 2 4 3 1]
    
76.             index:  0 1 2 3 4
    
77.             
    
78.         # of rectangles created by the cur column =
    
79.             (the index of the cur column - the index of the previous column with lower height)
    
80.             * the height of cur column
    
81.             + the submatries owing to the previous column with lower height
    
82.         
    
83.         we store the # of rectangle with the index, like: (index, # of rectangle of the cur column)
    
84.             
    
85.         Once you find h[3] = 3 which is not increasing,
    
86.             you pop items from stack (i, previous rectangle),
    
87.             until the item on the top of the stack has a lower height
    
88.             
    
89. 
    
90. 
    
91.         '''
    
92.         col = len(mat[0])
    
93.         res = 0
    
94.         h = [0 for _ in range(col)]
    
95.         
    
96.         for row in mat:
    
97.             stack = [(-1, 0)]
    
98.             
    
99.             for i in range(col):
    
100.                
     
101.                 h[i] = h[i] + 1 if row[i] == 1 else 0 # calculate the height  
     
102.                
     
103.                 while stack and len(stack) > 1 and h[stack[-1][0]] > h[i]:
     
104.                     stack.pop()
     
105.                
     
106.                 # the rectangles created by cur column
     
107.                 width = i - stack[-1][0]
     
108.                 plus = stack[-1][1]
     
109.                 cur = width*h[i] + plus
     
110.                
     
111.                 stack.append((i, cur))
     
112.                 res += cur
     
113.             print(h)
     
114.         return res

复制代码

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

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

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

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

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

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