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

骨骼面试有一类比较Tricky的题目，即单调队列 Monotonic Queue / 单调栈 Monotonic Stack
通过单调队列，可以把复杂度降到O(n)，主要覆盖Stack, Sliding Window, Two Pointers, Linked List/Queue, HashTable/HashMap等算法和数据结构，分类参考主贴


G家6个月内
LC42. Trapping Rain Water
LC84. Largest Rectangle in Histogram (单调递增

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

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

e OOD + 单调递增栈)
LC907. Sum of Subarray Minimums, 微软
LC1019. Next Greater Node In Linked List, FB 亚麻

后面会把做完的题跟贴。抛砖引玉，希望各路高手能把好理解、好记的解法贴出来。

1499应该也归属于这一类吧

您好！
本帖隐藏的内容需要积分高于 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

复制代码

加个1504

__jind 发表于 2020-7-12 04:47
加个1504

谢谢，不确定。如果有相应解法或链接，麻烦贴出来

您好！
本帖隐藏的内容需要积分高于 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

46, 84, 862三道Hard先跳过，有好的解法，麻烦贴出来，解释一下

更正 901. Online Stock Span 是G家的题，还是7月新题

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

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