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？这似乎是命令式语言中的一个好问题,确实在使用其他语言的堆栈溢出时有这个答案,但我不知道从哪里开始使用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

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

[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

然后,将每个数字解释为建筑物的高度,每一行都会减少为天际线问题:

鉴于建筑物的高度,找到最大的矩形横幅,完全适合天际线(即建筑物的轮廓).

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

                            +
         +                  +
     +   +                  # # #
     +   # # #            + # # #
     + + # # #            + # # #
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)}