algorithm - Haskell 中全 1 的最大平方

Question

如果我有一个矩阵

m = 0 0 1 1 0
    0 1 1 1 0
    1 0 1 1 1
    1 1 1 1 1
    0 1 1 1 1

我如何找到 m 的最大 nXn 子矩阵，它只是 1？这在命令式语言中似乎是一个不错的问题，并且确实在 Stack overflow using other languages 上有这个问题的答案，但我不知道从哪里开始使用 Haskell。

我们可以假设m表示为

m = [ [0, 0, 1, 1, 0]
    , [1, 1, 1, 0, 0]
    , [1, 0, 1, 1, 1]
    , [1, 1, 1, 1, 1]
    , [0, 1, 1, 1, 1]
    ]

如果有帮助。在这种情况下，答案是右下角的 3x3 子矩阵。

Answer 1

最佳 O(n^2) 解决方案可以仅使用列表和右折叠来完成 ⁽¹⁾。我还概括为最大面积子矩形，而不仅仅是正方形。仅限于正方形是一个简单的修改 ⁽²⁾。

import Control.Monad (ap)
import Data.Ord (comparing)

data Rect = Rect {
    row    :: Int, -- lower left row index
    col    :: Int, -- lower left column index
    width  :: Int,
    height :: Int
    } deriving (Show, Eq)

instance Ord Rect where  -- compare on area
    compare = comparing $ \a -> width a * height a

想法是，首先，在每个单元格中，向上计数 ones，直到达到零。对于问题中的示例，这将是:

[0,0,1,1,0]       [0,0,1,1,0]
[1,1,1,0,0]       [1,1,2,0,0]
[1,0,1,1,1]  >>>  [2,0,3,1,1]
[1,1,1,1,1]       [3,1,4,2,2]
[0,1,1,1,1]       [0,2,5,3,3]

并且可以通过正确的折叠来完成:

count :: Foldable t => t [Int] -> [[Int]]
count = ($ repeat 0) . foldr go (const [])
    where
    go x f = ap (:) f . zipWith inc x
    inc 0 = const 0
    inc _ = succ

然后，将每个数字解释为建筑物的高度，每一行都简化为一个天际线问题:

Given height of buildings, find the largest rectangular banner which fits entirely under the skyline (i.e. outline of buildings).

例如，天际线和最后两行的最佳矩形横幅如下(横幅标有#):

                            +
         +                  +
     +   +                  # # #
     +   # # #            + # # #
     + + # # #            + # # #
4th: 3 1 4 2 2     5th: 0 2 5 3 3

这个问题可以在每一行的线性时间内解决，方法是维护一个高度增加的建筑物堆栈(列表)。每当从堆栈中弹出一个项目时，我们都会更新当前的最佳解决方案:

solve :: Foldable t => t [Int] -> Rect
solve = maximum . zipWith run [0..] . count
    where
    run ri xs = maximum $ foldr go end xs 1 [(0, 0)]
        where
        end = go 0 $ \_ _ -> []
        go x f i ((_, y): r@((k, _):_))
            | x <= y = Rect ri k (i - k - 1) y: go x f i r
        go x f i y = f (i + 1) $ (i, x): y

然后，

\> solve [[0,0,1,1,0],[1,1,1,0,0],[1,0,1,1,1]]
Rect {row = 2, col = 2, width = 3, height = 1}

\> solve [[0,0,1,1,0],[1,1,1,0,0],[1,0,1,1,1],[1,1,1,1,1]]
Rect {row = 3, col = 2, width = 3, height = 2}

\> solve [[0,0,1,1,0],[1,1,1,0,0],[1,0,1,1,1],[1,1,1,1,1],[0,1,1,1,1]]
Rect {row = 4, col = 2, width = 3, height = 3}

---

<子>1。这是最佳的，因为它与矩阵元素的数量成线性关系，并且您不能在这里做得比线性更好。
2. 为了限制为正方形，您只需将 compare 函数中使用的 lambda 更改为:\a -> min (width a) (height a)