LeetCode.最大矩形

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

• 示例 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

  解法：

  object MaximalRectangle {
       def main(args: Array[String]): Unit = {
  
            val arr1 = Array(
                 Array('0', '1'),
                 Array('1', '0')
            )
  
            println(maximalRectangle(arr1))
  
            val arr = Array(
                 Array('1', '0', '1', '0', '0'),
                 Array('1', '0', '1', '1', '1'),
                 Array('1', '1', '1', '1', '1'),
                 Array('1', '0', '0', '1', '0')
            )
            println(maximalRectangle(arr))
       }
  
       def maximalRectangle(matrix: Array[Array[Char]]): Int = {
            if (matrix.length == 0) return 0
            val dp = new Array[Int](matrix(0).length)
            var maxArea = 0
  
            for (i <- 0 until matrix.length) {
                 for (j <- 0 until matrix(i).length) {
                      if (matrix(i)(j) == '1') dp(j) = dp(j) + 1 else dp(j) = 0
                 }
                 maxArea = Math.max(maxArea, largestRectangleArea3(dp))
            }
  
            maxArea
       }
  
       def largestRectangleArea3(height: Array[Int]): Int = {
            if (height.length == 0) return 0
  
            var list: List[Int] = height.toList
            val heights = new ListBuffer[Int]()
            heights ++= list
            heights += 0
  
            var res = 0
            val st = new java.util.Stack[Int]()
            var i = 0
  
            while (i < heights.length) {
                 if (st.isEmpty || heights(i) > heights(st.peek())) {
                      st.push(i)
                      i += 1
                 } else {
                      val curr = st.peek()
                      st.pop()
                      val area = heights(curr) * (if (st.isEmpty()) i else (i - 1 - st.peek()))
                      res = Math.max(res, area)
                 }
            }
  
            res
       }
  }