程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> LeetCode Maximal Rectangle淺析

LeetCode Maximal Rectangle淺析

編輯:關於C++

LeetCode解題之Maximal Rectangle


原題

一個矩陣僅包含1和0,找出其中面積最大的只含有1的矩形,並返回它的面積。

注意點:

矩陣中的元素類型是字符串

例子:

輸入:

matrix = 
[['1', '1', '0', '1', '0', '1'],
 ['0', '1', '0', '0', '1', '1'],
 ['1', '1', '1', '1', '0', '1'],
 ['1', '1', '1', '1', '0', '1']]

輸出: 8

解題思路

這道題和 Largest Rectangle in Histogram 的關系非常密切。如果把1看做柱狀的實體,那麼這就是一個中間有空缺的柱狀圖。依次遍歷每一行,把每一行當做柱狀圖的底邊,就能將題目轉化為Largest Rectangle in Histogram來解決。如以第二行為底,則是這樣一個柱狀圖[1,2,0,0,1,1],容易發現規律:遍歷下一行時,如果是1,則在原來的高度上加一,否則將高度置為0。

AC源碼

class Solution(object):
    def maximalRectangle(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        if not matrix or not matrix[0]:
            return 0
        n = len(matrix[0])
        heights = [0 for __ in range(n + 1)]
        result = 0
        for row in matrix:
            for i in range(n):
                heights[i] = heights[i] + 1 if row[i] == '1' else 0
            stack = [-1]
            for i in range(n + 1):
                while heights[i] < heights[stack[-1]]:
                    h = heights[stack.pop()]
                    w = i - stack[-1] - 1
                    result = max(result, h * w)
                stack.append(i)
        return result


if __name__ == "__main__":
    assert Solution().maximalRectangle([['1', '1', '0', '1', '0', '1'],
                                        ['0', '1', '0', '0', '1', '1'],
                                        ['1', '1', '1', '1', '0', '1'],
                                        ['1', '1', '1', '1', '0', '1']]) ==8
   
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved