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

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


G家6个月内
LC42. Trapping Rain Water<

您好！
本帖隐藏的内容需要积分高于 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应该也归属于这一类吧

42. Trapping Rain Water
根据下面这个帖子，写了一个Python版本
https://www.cnblogs.com/grandyang/p/4402392.html
跟前面几题不一样的是，用到栈里两个数，一个作为左边的高，一个作为底。
栈是一个递减栈，这样才能形成一个坑。算坑里的水，是一个个底往上算。
    def trap(self, height: List[int]) -> int:
        s=[]
        r=0
        for i in range(len(height)):
            while s and height[i]>height[s[-1]]:
                t = s.pop()
                if s:
                    r = r + (min(height[i], height[s[-1]]) - height[t]) * (i-s[-1]-1)
            s.append(i)
        return r

min(height[i], height[s[-1]]) - height[t] 两边高取小，再把前面算过的底去掉
i-s[-1]-1 两边的距离减一，紧挨着盛不了水

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

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

LC239. Sliding Window Maximum (有界最大值单调递减栈)

滑动窗口沿着数组滑动，算出每个窗口内的最大值。
题目有个办法就是用Heap把窗口内的元素排序。每次滑动把尾数删掉，新数加入。复杂度是O(nlogk)，因为heap的操作是O(N)这里的N是Heap的size，所以是O(k)。单调栈可以把复杂度降到O(n)，每次新数把比其小的栈顶元素pop。

    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        max = []
        l = 0
        r = 0
        stack = []
        #初始化栈
        while r< k:
            while len(stack) and stack[-1]<nums[r]:#新数入栈前，把栈顶比其小的都弹出
                stack.pop()
            stack.append(nums[r])#新数入栈
            r=r+1
        max.append(stack[0])#第一个窗口的最大值
        #滑动窗口
        while r<len(nums):
            if len(stack) and stack[0]==nums[l]:#如果栈底刚出窗口，移除
                stack.pop(0)
            l = l +1
            while len(stack) and stack[-1]<nums[r]:#新数入栈前，把栈顶比其小的都弹出
                stack.pop()
            stack.append(nums[r])#新数入栈
            max.append(stack[0])#取最大值
            r = r +1
        return max

刚出窗口的数2种情况
原窗口内最大值，在栈底，被移除。
原窗口内不是最大值，不在栈内，忽略。

Window position               Max       Stack          尾数
---------------                       -----        ------            -----
[1  3  -1] -3  5  3  6  7       3             [3, -1]         1，不是最大，不在栈内，忽略
1 [3  -1  -3] 5  3  6  7       3             [3, -1, -3]    3，最大，栈底，移除
1  3 [-1  -3  5] 3  6  7       5             [5]               -1，不是最大，不在栈内
1  3  -1 [-3  5  3] 6  7       5             [5, 3]           -3，不是最大，不在栈内
1  3  -1  -3 [5  3  6] 7       6             [6]               5，不是最大，不在栈内
1  3  -1  -3  5 [3  6  7]      7             [7]     

无注释版

    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        max = []
        l = 0
        r = 0
        stack = []
        while r< k:
            while len(stack) and stack[-1]<nums[r]:
                stack.pop()
            stack.append(nums[r])
            r=r+1
        max.append(stack[0])
        while r<len(nums):
            if len(stack) and stack[0]==nums[l]:
                stack.pop(0)
            l = l +1
            while len(stack) and stack[-1]<nums[r]:
                stack.pop()
            stack.append(nums[r])
            max.append(stack[0])
            r = r +1
        return max

关于复杂度，
对于栈顶元素，1, 比新数大，则每个新数比较一次，不入栈，即新数的比较次数是常数。2，新数最大，新数跟每个栈内数比较一次，每个老数的比较次数是常数。所以整体入栈操作常数。

最近练Python，欢迎有其语言解法或者精简python解法跟帖

LC1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit  
给定一个数组，算出子数组范围不超过limit的size。相比239，需要多维护一个最小数的栈。
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        min = []
        max = []
        l = 0
        r = 0
        size =0
        while r < len(nums):
            #新数入栈最小栈
            while len(min) and min[-1] > nums[r]:
                min.pop()
            min.append(nums[r])
            #新数入栈最大栈
            while len(max) and max[-1] < nums[r]:
                max.pop()
            max.append(nums[r])
            r =  r + 1
            
            while l < r:
                #如果最大值最小差值小于limit，更新size      
                if max[0] - min[0] <= limit:
                    if r-l > size:
                        size = r-l
                    break
                #如果最左边在栈底，则删除
                if min[0] == nums[l]:
                    min.pop(0)
                if max[0] == nums[l]:
                    max.pop(0)
                l = l +1
        return size

LC496. Next Greater Element I

数组1是数组2的子集。在数组2中找每个数组1元素，在数组2内其后第一个比其大的元素位置。暴力解法从数组2中找相应元素，然后往后一个个比较，找到比它大的为止。
单调栈方法：用一个栈维护数组2从小到大的序列。每次入栈，如果新数比栈顶大，用Map记录新数作为栈顶的下一个最大数。
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        stack = []
        map = {}
        #遍历数组2，找出每个数是否是栈顶的下一个最大(NGN)
        for i in nums2:
            #如果新数比栈顶大，说明其是栈顶的NGN
            while len(stack) and stack[-1] < i:
                #用Map记录栈顶指向新数，然后出栈
                map[stack.pop()]=i
            stack.append(i)
        result = []
        #遍历数组1，从Map取对应元素NGN
        for i in nums1:
            if i in map:
                result.append(map[i])
            else:
                result.append(-1)
        return result

LC122. Best Time to Buy and Sell Stock II   
给出股票每天价格，计算累计可以挣的钱最大值。限制，只有一笔买卖可以进行。股票就是低买高卖。找出每次单调递增的头尾，头买尾卖，即是最大收益。
    def maxProfit(self, prices: List[int]) -> int:
        stack = []
        m = 0
        for p in prices:
            #价格单调递增结束
            if len(stack) and p < stack[-1]:
                if len(stack)>1:
                    m = m + stack[-1] - stack[0]
                stack = []
            stack.append(p)
       #补充最后一个单调递增
        if len(stack)>1:
            m = m + stack[-1] - stack[0]
        return m

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

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

901. Online Stock Span
给出股票的价格列表，求每个股票最长增长区间，即前几天的股票价格不比其高。
class StockSpanner:

    def __init__(self):
        self.stack=[]
        self.map={}
        self.count=0

    def next(self, price: int) -> int:
        self.count =  self.count + 1
        self.map[price] = self.count
        #把栈顶小于当前价格都出栈
        while len(self.stack) and self.stack[-1] <= price:
            self.stack.pop()
        self.stack.append(price)
        #当前价格的位置，减去第一个比其大的价格位置
        if len(self.stack)>1:
            return self.count - self.map[self.stack[-2]]
        else:
            return self.count