[Swift]LeetCode85. 最大矩形 | Maximal Rectangle
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
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] = 0
14 }
15 }
16 ans = max(ans,getLargetRect(rowArr))
17 }
18 return ans
19 }
20
21 func getLargetRect(_ rowArr:[Int]) -> Int {
22 var stack = [Int]()
23 var maxArea = 0
24 for (index,height) in rowArr.enumerated() {
25 while let last = stack.last, rowArr[last] > height {
26 stack.removeLast()
27 var width = 0
28 if stack.isEmpty {
29 width = index
30 } else {
31 width = index - stack.last! - 1
32 }
33 maxArea = max(maxArea, width * rowArr[last] )
34 }
35
36 stack.append(index)
37 }
38 return maxArea
39 }
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..<n).reversed() {
11 var count = 0
12 for j in (0..<m).reversed() {
13 if matrix[i][j] == "1" {
14 count += 1
15 } else {
16 count = 0
17 }
18 mark[i][j] = count
19 }
20 }
21
22 var result = 0
23 for i in 0..<n {
24 for j in 0..<m {
25 var minColumn = m
26 var row = i
27 while row < n && mark[row][j] != 0 {
28 minColumn = min(minColumn, mark[row][j])
29 result = max(result, (row - i + 1) * minColumn)
30 row += 1
31 }
32 }
33 }
34 return result
35 }
36 }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 = 0
11
12 for i in 0..<matrix.count {
13
14 for j in 0..<matrix[i].count {
15
16 if matrix[i][j] == "1" {
17
18 heights[j] += 1
19
20 } else {
21 heights[j] = 0
22 }
23 }
24
25 s = max(s, largestRectangleArea(heights))
26 }
27
28 return s
29 }
30
31 func largestRectangleArea(_ heights: [Int]) -> Int {
32
33 if heights.count == 0 {
34 return 0
35 }
36
37 var myHeights: [Int] = heights
38 myHeights.append(0)
39
40
41 var s = 0
42 //swift中没有栈,使用数组代替,永远操作最后一位
43 var stack: [Int] = []
44 var i = 0
45
46 while i < myHeights.count {
47
48 if stack.count == 0 || myHeights[stack.last!] < myHeights[i] {
49
50 stack.append(i)
51 i += 1
52 } 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 s
63 }
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 = 0
12 for i in 0..<m {
13 var currentLeft = 0
14 var currentRight = n
15 for j in 0..<n {
16 if (matrix[i][j] == "1") {
17 left[j] = max(left[j], currentLeft)
18 height[j] = height[j] + 1
19 } else {
20 left[j] = 0
21 currentLeft = j + 1
22 height[j] = 0
23 }
24 if (matrix[i][n - j - 1] == "1") {
25 right[n - j - 1] = min(right[n - j - 1], currentRight)
26 } else {
27 currentRight = n - j - 1
28 right[n - j - 1] = n
29 }
30 }
31 for j in 0..<n {
32 result = max(result, (right[j] - left[j]) * height[j])
33 }
34 }
35 return result
36 }
37 }436ms
1 class HistoArea {
2 func largestRectangleArea(_ heights: [Int]) -> Int {
3 var stack = [Int]()
4 var max = 0
5 for i in 0..<heights.count {
6 if stack.count == 0 || heights[i]>=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 = area
13 }
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 = area
22 }
23 }
24 return max
25 }
26
27 func eval(_ stack: inout [Int], _ heights: [Int], _ end: Int) -> Int {
28 let idx = stack.last!
29 stack.removeLast()
30 var area = 0
31
32 if let start = stack.last {
33 area = heights[idx]*(end-start-1)
34 } else {
35 area = heights[idx]*end
36 }
37 return area
38 }
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 0
47 }
48 for i in 0..<matrix[0].count {
49 histogram.append(0)
50 }
51 var maxArea = 0
52
53 for i in 0..<matrix.count {
54 for j in 0..<matrix[0].count {
55 if matrix[i][j] == "1" {
56 histogram[j] += 1
57 } else {
58 histogram[j] = 0
59 }
60 }
61 let area = hist.largestRectangleArea(histogram)
62 if area > maxArea {
63 maxArea = area
64 }
65 }
66 return maxArea
67 }
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 = 0
11
12 for row in 0..<rLen {
13 var stack = [Int]()
14 for i in 0..<(cLen + 1) {
15 if i < cLen {
16 if matrix[row][i] == "1" {
17 h[i] += 1
18 } else {
19 h[i] = 0
20 }
21 }
22 if stack.isEmpty || h[stack.last!] <= h[i] {
23 stack.append(i)
24 } else {
25 while !stack.isEmpty && h[i] < h[stack.last!] {
26 let top = stack.removeLast()
27 let area = h[top] * (stack.isEmpty ? i : (i - stack.last! - 1))
28 if area > maxValue {
29 maxValue = area
30 }
31 }
32 stack.append(i)
33 }
34 }
35 }
36 return maxValue
37 }
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..<n).reversed() {
11 var count = 0
12 for j in (0..<m).reversed() {
13 if matrix[i][j] == "1" {
14 count += 1
15 } else {
16 count = 0
17 }
18 mark[i][j] = count
19 }
20 }
21
22 var result = 0
23 for i in 0..<n {
24 for j in 0..<m {
25 var minColumn = m
26 var row = i
27 while row < n && mark[row][j] != 0 {
28 minColumn = min(minColumn, mark[row][j])
29 result = max(result, (row - i + 1) * minColumn)
30 row += 1
31 }
32 }
33 }
34 return result
35 }
36 }