iT邦幫忙

1

LeectCode解題pattern- Monotone Stack

今天來分享一個在leetcode中很實用的解題技巧- Monotone Stack,
顧名思義,就是一個stack裡面維持單調遞增或遞減,
詳情可參考leetcode all in one 的LeetCode Monotone Stack Summary 单调栈小结這篇文章,
小鹿覺得講的還蠻生動的

隨著leetcode的題目愈來愈多,快要接近2000題了,
想要有效率的刷題,
小鹿覺得需要系統化的學習,學一道觀念,
能夠套用在多道題目中,
一次將類似題一起解完,練習舉一反三,
就會慢慢熟悉這個概念。

經典題- 84. Largest Rectangle in Histogram

Monotone Stack中最經典的一道題大概屬這道吧,
https://ithelp.ithome.com.tw/upload/images/20210509/20135919NpdQRyVymg.png

這是一道Hard題,給定一個陣列表示直方圖,
求直方圖中最大的長方形面積?

若沒看過詳解的話,恐怕很難自己想出來,
普通想到的就是窮舉所有的子陣列,
長方積面積可以由min(子陣列)*len(子陣列)得到,
這樣時間複雜度為O(n^3),實在是太慢了。
用Monotone Stack的技巧可以將時間複雜度降到O(n)

直接來欣賞做法吧,
我們維護一個單調遞增的stack,
小的元素進來可以把stack裡面大的元素踢出去,
當元素出stack的時候可以計算以高度為最小值,
向左、右延伸最多可以到多寬

python程式碼:

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        """
        計算直方圖的最大面積
        """
        res = 0
        stack = [-1] # 較特別,存的是index而不是直接存高度,因為要留存寬度訊息。trick放入index「-1」
        heights.append(0) # trick: 在陣列尾巴放一個0以把stack內元素拋出
        for i in range(len(heights)):    
            while stack[-1]!=-1 and heights[stack[-1]] >= heights[i]:
                cur = stack.pop()  
                res = max(res, heights[cur] * (i-stack[-1]-1))
            stack.append(i)
        return res

意外的是,程式碼僅有短短十行而已,
若熟悉的話可以破解leetcode其它多道類似題,
小鹿改寫的python程式碼中加入一些trick:

  • stack存的是index而不是直接存高度,因為要留存寬度訊息。
  • stack一開始放入index「-1」,方便直接計算寬度
  • heights一定都是正整數,尾巴多放一個0以把stack內元素拋出

實際舉個例子看迴圈內在做什麼:
input:
陣列元素- [1,3,4,2]+[0]
index - 0 1 2 3 4

首先維護一個單調遞增的stack,
一開始stack內依序堆了元素[1,3,4]
隨後元素2進來了,
把元素4踢掉,得到結果4*(3-1-1)=4
https://ithelp.ithome.com.tw/upload/images/20210509/20135919J9XGOX9Q8B.png
把3踢掉,得到結果3*(3-0-1)=6
https://ithelp.ithome.com.tw/upload/images/20210509/20135919YNnVYoVNdv.png

最後元素0進來,
把元素2踢掉,得到結果2*(4-0-1)=6
https://ithelp.ithome.com.tw/upload/images/20210509/20135919Hxl3ZfA7lN.png
把元素1踢掉,得到結果1*(4-(-1)-1)=4
https://ithelp.ithome.com.tw/upload/images/20210509/201359193zmvhF7Izh.png
過程中出現的最大矩形面積為6

類似題分享

底下這幾題為84. Largest Rectangle in Histogram的類似題,熟悉套路的話,
這些難題也不那麼Hard了。
都是拿84題做變形修改,
想自我練習的朋友可以先不看小鹿的解答自行嘗試看看

85. Maximal Rectangle
907. Sum of Subarray Minimums
1793. Maximum Score of a Good Subarray
1856. Maximum Subarray Min-Product

底下分享小鹿舉一反三的做法囉

Hard- 85. Maximal Rectangle

https://ithelp.ithome.com.tw/upload/images/20210510/20135919K29bUR41Sh.png
本題給定一個由0和1的矩陣,要求最大的長方形面積。
我們可以row by row的掃,
對於每個row,看上面的長條多長,
譬如說這張圖
https://ithelp.ithome.com.tw/upload/images/20210510/20135919nbkCg9lhdZ.png
就對應長條[3,1,3,2,2]
然後對每個row套用「84. Largest Rectangle in Histogram」的演算法即可

這邊需要做一個pre-process,
由上往下記錄連續的1,
譬如說

["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]

would become
[1, 0, 1, 0, 0], 
[2, 0, 2, 1, 1], 
[3, 1, 3, 2, 2], 
[4, 0, 0, 3, 0]   

程式碼:

def largestRectangleArea(heights):
    """
    計算直方圖的最大面積
    """
    res = 0
    stack = [-1] # 較特別,存的是index而不是直接存高度,因為要留存寬度訊息。trick放入index「-1」
    heights.append(0) # trick: 在陣列尾巴放一個0以把stack內元素拋出
    for i in range(len(heights)):        
        while stack[-1]!=-1 and heights[stack[-1]] >= heights[i]:
            cur = stack.pop()  
            res = max(res, heights[cur] * (i-stack[-1]-1))
        stack.append(i)
    return res


def store_continuous(matrix):
    for c in range(len(matrix[0])):
        freq = 0
        for r in range(len(matrix)):
            if matrix[r][c] == "1":
                freq += 1
                matrix[r][c] = freq
            else:
                matrix[r][c] = 0
                freq = 0


class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if not (matrix and matrix[0]):
            return 0
        store_continuous(matrix)
        return max([largestRectangleArea(row) for row in matrix])
        

Medium- 907. Sum of Subarray Minimums

https://ithelp.ithome.com.tw/upload/images/20210510/201359197qtKk2JdNa.png

本題要求所有子陣列的最小值總和,
小鹿覺得本題比上面兩題來得難,
因為從題目來看有點不易聯想到本題與求直方圖最大面積有什麼關係。

普通想到這題就是窮舉所有的子陣列,
然後去計算每個子陣列的min,再加總,
這樣時間複雜度為O(n^3),太慢了

技巧在於,求直方圖最大面積的算法中,
每當元素出stack的時候,
可以知道該元素向左、右延伸最多可以到多寬,
因此我們可以算出每個元素在出stack的時候,
該元素是幾個子陣列的最小值(左邊可能的元素個數0~(cur-stack[-1]-1)個,乘上右邊可能的子陣列個數0~(i-cur-1)個)

程式碼幾乎只改了res += heights[cur]*(i-cur)*(cur-stack[-1])

class Solution:
    def sumSubarrayMins(self, arr: List[int]) -> int:
        res = 0
        stack = [-1] # 較特別,存的是index而不是直接存高度,因為要留存寬度訊息。trick放入index「-1」
        heights = arr+[0] # trick: 在陣列尾巴放一個0以把stack內元素拋出
        for i in range(len(heights)):    
            while stack[-1]!=-1 and heights[stack[-1]] >= heights[i]:
                cur = stack.pop()
                res += heights[cur]*(i-cur)*(cur-stack[-1])
            stack.append(i)
        return res%(10**9+7)

Hard- 1793. Maximum Score of a Good Subarray

https://ithelp.ithome.com.tw/upload/images/20210510/20135919nRFPAITJZv.png
這題定義了subarray的score計算公式min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1)
其實仔細看的話,這根本就是計算直方圖面積的公式,
跟84. Largest Rectangle in Histogram那題的差別只在有跨越nums[k]的矩形需要被計算最大值,
因此程式碼多卡一層if stack[-1]<k<i:也就解了

class Solution:
    def maximumScore(self, nums: List[int], k: int) -> int:
        """
        本題思路其實與84. Largest Rectangle in Histogram一樣,
        差別在只有跨越nums[k]的矩形需要被計算最大值
        """
        res = 0
        stack = [-1] # 較特別,存的是index而不是直接存高度,因為要留存寬度訊息。trick放入index「-1」
        heights = nums+[0] # trick: 在陣列尾巴放一個0以把stack內元素拋出
        for i in range(len(heights)):    
            while stack[-1]!=-1 and heights[stack[-1]] >= heights[i]:
                cur = stack.pop()
                if stack[-1]<k<i:
                    res = max(res, heights[cur] * (i-stack[-1]-1))
            stack.append(i)
        return res

Medium- 1856. Maximum Subarray Min-Product

https://ithelp.ithome.com.tw/upload/images/20210510/20135919cu7zuzYCT5.png

本題與84. Largest Rectangle in Histogram的思路也是非常像的,
差別在於直方圖面積是min(子陣列)*len(子陣列)
本題要計算min(子陣列)*sum(子陣列)
至於要如何快速求出多個子陣列的總和,
可以用「accumulate sum」的技巧,
程式碼從原本的res = max(res, heights[cur] * (i-stack[-1]-1))改成
res = max(res, nums[cur] * (accum_sum[i]-accum_sum[stack[-1]+1]))即可

程式碼:

from itertools import accumulate
class Solution:
    def maxSumMinProduct(self, nums: List[int]) -> int:
        res = 0
        stack = [-1] # 較特別,存的是index而不是直接存高度,因為要留存寬度訊息。trick放入index「-1」
        heights = nums +[0] # trick: 在陣列尾巴放一個0以把stack內元素拋出
        accum_sum = list(accumulate(nums, initial=0))
        for i in range(len(heights)):    
            while stack[-1]!=-1 and heights[stack[-1]] >= heights[i]:
                cur = stack.pop()  
                res = max(res, nums[cur] * (accum_sum[i]-accum_sum[stack[-1]+1]))
            stack.append(i)
        return res%(10**9+7)

尚未有邦友留言

立即登入留言