重庆工程建设招标投标交易信息网,广州外贸seo优化,买公司的网站建设,网站透明flash题目
给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵#xff0c;找出只包含 1 的最大矩形#xff0c;并返回其面积。
示例 1#xff1a;
输入#xff1a;matrix [[“1”,“0”,“1”,“0”,“0”],[“1”,“0”,“1”,“1”,“1”],[“1”,“1”,“1”,…题目
给定一个仅包含 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
思路
最大矩形面积问题可以使用栈来解决结合柱状图的特性。下面我将详细解释解题思路并提供关键算法和算法思想的说明。
解题思路
对于每一行我们可以将每个元素的值视为当前位置向上的高度。我们可以根据每一行的高度构建一个柱状图然后使用栈来计算柱状图中的最大矩形面积。 对于每一行我们构建一个高度数组 heights其中 heights[j] 表示从当前行的第 j 列向上的连续 1 的数量。我们可以根据上一行的高度数组和当前行的元素来更新这个数组。 对于 heights 数组我们使用栈来辅助计算最大矩形面积。我们遍历 heights 数组如果当前高度大于栈顶高度就将当前索引入栈。否则我们弹出栈顶索引并计算以该高度为高的矩形面积宽度为当前索引与弹出索引之间的距离。我们不断更新最大面积直到栈为空或者当前高度大于栈顶高度。
关键算法和算法思想
栈是解决这个问题的关键算法思想。通过使用栈我们可以维护一个递增的高度序列当遇到下降的高度时我们可以计算以当前高度为高的矩形面积利用栈中保存的索引信息。
代码
object Solution {def maximalRectangle(matrix: Array[Array[Char]]): Int {if (matrix.isEmpty) return 0val rows matrix.lengthval cols matrix(0).lengthvar maxArea 0val heights Array.fill(cols)(0)def largestRectangleArea(heights: Array[Int]): Int {val stack collection.mutable.Stack[Int]()var maxArea 0for (i - 0 until heights.length) {while (stack.nonEmpty heights(i) heights(stack.top)) {val height heights(stack.pop())val width if (stack.isEmpty) i else i - stack.top - 1maxArea math.max(maxArea, height * width)}stack.push(i)}while (stack.nonEmpty) {val height heights(stack.pop())val width if (stack.isEmpty) heights.length else heights.length - stack.top - 1maxArea math.max(maxArea, height * width)}maxArea}for (i - 0 until rows) {for (j - 0 until cols) {if (matrix(i)(j) 1) heights(j) 1else heights(j) 0}maxArea math.max(maxArea, largestRectangleArea(heights))}maxArea}
}// 示例
val matrix 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)
)
val result Solution.maximalRectangle(matrix)
println(result) // 输出6
