前言

本題為 LeetCode 前 100 高頻題

本題由于沒有合適答案為以往遺留問題，最近有時(shí)間將以往遺留問題一一完善。

我們社區(qū)陸續(xù)會(huì)將顧毅（Netflix 增長(zhǎng)黑客，《iOS 面試之道》作者，ACE 職業(yè)健身教練。）的 Swift 算法題題解整理為文字版以方便大家學(xué)習(xí)與閱讀。

LeetCode 算法到目前我們已經(jīng)更新到 84 期，我們會(huì)保持更新時(shí)間和進(jìn)度（周一、周三、周五早上 9:00 發(fā)布），每期的內(nèi)容不多，我們希望大家可以在上班路上閱讀，長(zhǎng)久積累會(huì)有很大提升。

不積跬步，無以至千里；不積小流，無以成江海，Swift社區(qū) 伴你前行。如果大家有建議和意見歡迎在文末留言，我們會(huì)盡力滿足大家的需求。

難度水平：困難

1. 描述

給定一個(gè)僅包含 0 和 1 、大小為 rows x cols 的二維二進(jìn)制矩陣，找出只包含 1 的最大矩形，并返回其面積。

2. 示例

示例 1

輸入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
輸出：6
解釋：最大矩形如上圖所示。

示例 2

輸入：matrix = []
輸出：0

示例 3

輸入：matrix = [["0"]]
輸出：0

示例 4

輸入：matrix = [["1"]]
輸出：1

示例 5

輸入：matrix = [["0","0"]]
輸出：0

提示：

• rows == matrix.length
• cols == matrix[0].length
• 1 <= row, cols <= 200
• matrix[i][j] 為 '0' 或 '1'

3. 答案

題解 1

class Solution {
   func maximalRectangle(_ matrix: [[Character]]) -> Int {
       if matrix.count == 0 || matrix[0].count == 0{
           return 0
       }
       var ans = 0
       var rowArr = Array(repeating:0,count:matrix[0].count + 1)
       for y in stride(from:0,to:matrix.count,by:1) {
           for x in stride(from:0,to:matrix[0].count,by:1) {
               if matrix[y][x] == "1" {
                   rowArr[x] += 1 
               } else {
                   rowArr[x] = 0
               }
           }
           ans = max(ans,getLargetRect(rowArr))
       }
       return ans
   }

   func getLargetRect(_ rowArr:[Int]) -> Int {
       var stack = [Int]()
       var maxArea = 0
       for (index,height) in rowArr.enumerated() {
           while let last = stack.last, rowArr[last] > height {
               stack.removeLast()
               var width = 0
               if stack.isEmpty {
                   width = index
               } else {
                   width = index - stack.last! - 1
               }
               maxArea = max(maxArea, width * rowArr[last] )
           }

           stack.append(index)
       }
       return maxArea
   }
}

題解 2

class Solution {
   func maximalRectangle(_ matrix: [[Character]]) -> Int {
       let n = matrix.count
       guard n > 0 else {
           return 0
       }
       let m = matrix[0].count

       var mark = Array(repeatElement(Array(repeatElement(0, count: m)), count: n))
       for i in (0..<n).reversed() {
           var count = 0
           for j in (0..<m).reversed() {
               if matrix[i][j] == "1" {
                   count += 1
               } else {
                   count = 0
               }
               mark[i][j] = count
           }
       }

       var result = 0
       for i in 0..<n {
           for j in 0..<m {
               var minColumn = m
               var row = i
               while row < n && mark[row][j] != 0 {
                   minColumn = min(minColumn, mark[row][j])
                   result = max(result, (row - i + 1) * minColumn)
                   row += 1
               }
           }
       }
       return result
   }
}

點(diǎn)擊前往 LeetCode 練習(xí)

關(guān)于我們

我們是由 Swift 愛好者共同維護(hù)，我們會(huì)分享以 Swift 實(shí)戰(zhàn)、SwiftUI、Swift 基礎(chǔ)為核心的技術(shù)內(nèi)容，也整理收集優(yōu)秀的學(xué)習(xí)資料。文章來源地址http://www.zghlxwxcb.cn/news/detail-497809.html

到了這里，關(guān)于LeetCode - #85 最大矩形（Top 100）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！