★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）➤博客园地址：山青咏芝（）➤GitHub地址：➤原文地址： ➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.
Example:
Input:[ ["1","0","1","0","0"], ["1","0","1","1","1"], ["1","1","1","1","1"], ["1","0","0","1","0"]]Output: 6
给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
示例:
输入:[ ["1","0","1","0","0"], ["1","0","1","1","1"], ["1","1","1","1","1"], ["1","0","0","1","0"]]输出: 6
160ms
1 class Solution { 2 func maximalRectangle(_ matrix: [[Character]]) -> Int { 3 if matrix.count == 0 || matrix[0].count == 0{ 4 return 0 5 } 6 var ans = 0 7 var rowArr = Array(repeating:0,count:matrix[0].count + 1) 8 for y in stride(from:0,to:matrix.count,by:1) { 9 for x in stride(from:0,to:matrix[0].count,by:1) {10 if matrix[y][x] == "1" {11 rowArr[x] += 1 12 } else {13 rowArr[x] = 014 }15 }16 ans = max(ans,getLargetRect(rowArr))17 }18 return ans19 }20 21 func getLargetRect(_ rowArr:[Int]) -> Int {22 var stack = [Int]()23 var maxArea = 024 for (index,height) in rowArr.enumerated() {25 while let last = stack.last, rowArr[last] > height {26 stack.removeLast()27 var width = 028 if stack.isEmpty {29 width = index30 } else {31 width = index - stack.last! - 132 }33 maxArea = max(maxArea, width * rowArr[last] )34 }35 36 stack.append(index)37 }38 return maxArea39 }40 } 168ms
1 class Solution { 2 func maximalRectangle(_ matrix: [[Character]]) -> Int { 3 let n = matrix.count 4 guard n > 0 else { 5 return 0 6 } 7 let m = matrix[0].count 8 9 var mark = Array(repeatElement(Array(repeatElement(0, count: m)), count: n))10 for i in (0.. 200ms
1 class Solution { 2 3 func maximalRectangle(_ matrix: [[Character]]) -> Int { 4 5 if matrix.count == 0 || matrix[0].count == 0 { 6 return 0 7 } 8 9 var heights = [Int](repeating: 0, count: matrix[0].count)10 var s = 011 12 for i in 0.. Int {32 33 if heights.count == 0 {34 return 035 }36 37 var myHeights: [Int] = heights38 myHeights.append(0)39 40 41 var s = 042 //swift中没有栈,使用数组代替,永远操作最后一位43 var stack: [Int] = []44 var i = 045 46 while i < myHeights.count {47 48 if stack.count == 0 || myHeights[stack.last!] < myHeights[i] {49 50 stack.append(i)51 i += 152 } else {53 54 let j = stack.last!55 stack.removeLast()56 57 //如果栈为空,说明数组第一位即构成矩形的左侧边界,此时索引大小即矩形长度58 //如果不为空,用栈顶索引和当前索引计算矩形长度59 s = max(s, myHeights[j]*(stack.isEmpty ? i : i - 1 - stack.last!))60 }61 }62 return s63 }64 65 } 416ms
1 class Solution { 2 func maximalRectangle(_ matrix: [[Character]]) -> Int { 3 guard matrix.count > 0 && matrix[0].count > 0 else { 4 return 0 5 } 6 let m = matrix.count 7 let n = matrix[0].count 8 var left = [Int](repeating: 0, count: n) 9 var right = [Int](repeating: n, count: n)10 var height = [Int](repeating: 0, count: n)11 var result = 012 for i in 0.. 436ms
1 class HistoArea { 2 func largestRectangleArea(_ heights: [Int]) -> Int { 3 var stack = [Int]() 4 var max = 0 5 for i in 0.. =heights[stack[stack.count-1]] { 7 stack.append(i) 8 } else { 9 while stack.count > 0 && heights[i] < heights[stack[stack.count-1]] {10 let area = eval(&stack, heights, i)11 if area > max {12 max = area13 }14 }15 stack.append(i)16 }17 }18 while stack.count > 0 {19 let area = eval(&stack, heights, heights.count)20 if area > max {21 max = area22 }23 }24 return max25 }26 27 func eval(_ stack: inout [Int], _ heights: [Int], _ end: Int) -> Int {28 let idx = stack.last!29 stack.removeLast()30 var area = 031 32 if let start = stack.last {33 area = heights[idx]*(end-start-1)34 } else {35 area = heights[idx]*end36 }37 return area38 }39 }40 41 class Solution {42 func maximalRectangle(_ matrix: [[Character]]) -> Int {43 let hist = HistoArea()44 var histogram = [Int]()45 if matrix.count == 0 {46 return 047 }48 for i in 0.. maxArea {63 maxArea = area64 }65 }66 return maxArea67 }68 } 452ms
1 class Solution { 2 func maximalRectangle(_ matrix: [[Character]]) -> Int { 3 if matrix.count == 0 || matrix[0].count == 0 { 4 return 0 5 } 6 7 let rLen = matrix.count 8 let cLen = matrix[0].count 9 var h = [Int](repeating: 0, count: cLen + 1)10 var maxValue = 011 12 for row in 0.. maxValue {29 maxValue = area30 }31 }32 stack.append(i)33 }34 }35 }36 return maxValue37 }38 } 588ms
1 class Solution { 2 func maximalRectangle(_ matrix: [[Character]]) -> Int { 3 let n = matrix.count 4 guard n > 0 else { 5 return 0 6 } 7 let m = matrix[0].count 8 9 var mark = Array(repeatElement(Array(repeatElement(0, count: m)), count: n))10 for i in (0..