算法：求最大子矩阵的面积

算法 0

版本：0
作者：陈小默
声明：禁止商业，禁止转载

题目：给定一个矩阵matrix，其中数据为整型，求其中全部是非0的所有矩形区域中 ，最大的矩形区域面积。

例如：

import java.util.*
/**
 *  project:DSA
 *  Copyright (C) <2016>  <陈小默>
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 *  Created by 陈小默 on 16/11/7.
 */
class Matrix(val column: Int, val raw: Int, m: IntArray? = null) {
    private val arr = IntArray(column * raw)
    init {
        if (m != null) {
            var index: Int
            finish@for (r in 0..raw - 1)
                for (c in 0..column - 1) {
                    index = r * column + c
                    if (index >= m.size) break@finish
                    arr[index] = m[index]
                }
        }
    }
    operator fun set(c: Int, r: Int, value: Int) {
        val index = r * column + c
        arr[index] = value
    }
    operator fun get(c: Int, r: Int): Int {
        val index = r * column + c
        return arr[index]
    }
    override fun toString(): String {
        val builder = StringBuilder().append('[')
        var index: Int
        for (r in 0..raw - 1) {
            if (r != 0) builder.appendln().append(' ')
            for (c in 0..column - 1) {
                if (c != 0) builder.append('\t')
                index = r * column + c
                builder.append(arr[index])
            }
        }
        return builder.append(']').toString()
    }
}
fun getMaxFromMap(map: HashMap<Int, Int>, index: Int): Int {
    var max = 0
    var max2: Int
    if (index != 0 && !map.containsKey(index)) {
        var maxIndex = 0
        map.filter { entry -> entry.key > index }.forEach { entry ->
            if (entry.value > maxIndex) maxIndex = entry.value
        }
        map[index] = maxIndex
    }
    var entry: MutableMap.MutableEntry<Int, Int>
    val it = map.iterator()
    while (it.hasNext()) {
        entry = it.next()
        max2 = entry.key * entry.value
        if (max2 > max) max = max2
        if (index < entry.key) it.remove()
        else map[entry.key] = entry.value + 1
    }
    return max
}
fun getMaxFromRaw(matrix: Matrix, raw: Int): Int {
    val map = HashMap<Int, Int>()
    var max = 0
    var max2: Int
    var preIndex = matrix[0, raw]
    var index: Int
    if (preIndex != 0) map[preIndex] = 1
    for (c in 1..matrix.column - 1) {
        index = matrix[c, raw]
        if (index > preIndex) {
            map.keys.forEach { key -> map[key] = map[key]!! + 1 }
            map[index] = 1
        } else if (index == preIndex) {
            if (index == 0) continue
            map.keys.forEach { key -> map[key] = map[key]!! + 1 }
        } else {
            max2 = getMaxFromMap(map, index)
            if (max2 > max) max = max2
        }
        if (c == matrix.column - 1 && index != 0) {
            max2 = getMaxFromMap(map, index)
            if (max2 > max) max = max2
        }
        preIndex = index
    }
    return max
}
fun genMaxMatrix(matrix: Matrix): Matrix {
    val mm = Matrix(matrix.column, matrix.raw)
    for (r in 0..mm.raw - 1)
        for (c in 0..mm.column - 1) {
            if (matrix[c, r] == 0) mm[c, r] = 0
            else if (r == 0) mm[c, r] = 1
            else mm[c, r] = mm[c, r - 1] + 1
        }
    return mm
}
fun countMatrix(matrix: Matrix): Int {
    val help = genMaxMatrix(matrix)
    var max = 0
    var max2: Int
    for (r in 0..help.raw - 1) {
        max2 = getMaxFromRaw(help, r)
        if (max < max2) max = max2
    }
    return max
}
fun maxArea(matrix: Matrix): Int {
    var maxArea = 0
    val raw = IntArray(matrix.column)
    for (r in 0..matrix.raw - 1) {
        for (c in 0..matrix.column - 1)
            raw[c] = if (0 == matrix[c, r]) 0 else raw[c] + 1
        println(Arrays.toString(raw))
        maxArea = Math.max(maxFromRow(raw), maxArea)
    }
    return maxArea
}
fun maxFromRow(raw: IntArray): Int {
    var maxArea = 0
    val stack = Stack<Int>()
    var j: Int
    var k: Int
    var curArea: Int
    for (i in 0..raw.size - 1) {
        while (!stack.isEmpty() && raw[i] <= raw[stack.peek()]) {
            j = stack.pop()
            k = if (stack.isEmpty()) -1 else stack.peek()
            curArea = (i - k - 1) * raw[j]
            maxArea = Math.max(maxArea, curArea)
        }
        stack.push(i)
    }
    while (!stack.isEmpty()) {
        j = stack.pop()
        k = if (stack.isEmpty()) -1 else stack.peek()
        curArea = (raw.size - k - 1) * raw[j]
        maxArea = Math.max(maxArea, curArea)
    }
    return maxArea
}