天际线上最小的最大矩形

Question

天际线是一个正整数数组，每个整数代表建筑物的高度。例如，如果我们有数组[1,3,4,2,5,3,3]，这将是ascii艺术中的天际线：

    #
  # #
 ## ###
 ######
#######

最大矩形是包含在天际线中时不能向任何方向扩展的矩形。例如，下面是一个最大矩形：

    #
  # #
 ## ###
 AAAAAA
#AAAAAA

但以下情况并非如此：

    #
  # #
 ## #BB
 ####BB
#####BB

因为您可以像这样将它扩展到左边：

    #
  # #
 ## CCC
 ###CCC
####CCC

这将是一个最大的矩形。

您的任务是以天际线作为输入(正整数列表)，并返回最小的最大矩形的面积。您可以假设输入的长度至少为1。

测试案例

[1] -> 1
[1,1] -> 2
[2,2,2] -> 6
[3,2,3] -> 3
[3,2,1] -> 3
[6,3,1,5] -> 4
[1,5,5,5] -> 4
[5,5,5,1] -> 4
[1,2,3,4] -> 4
[1,2,3,4,5] -> 5
[1,1,1,5,1,1,1] -> 5
[10,3,1,1,1,1,1,3,10] -> 6

这是代码-高尔夫，所以最短的字节在任何语言赢！

Answer 1

J，61字节

0<./@-.~[:,[:(~.*#-I.@~:)"1@|:[:(0-.~#;._1@,~&0)"1@|.@|:#"+&1

在网上试试！

我认为最终的测试用例应该是6，而6 3 1 5应该返回4，需要通过OP进行验证。

奇怪的长，但也许是个有趣的主意..。

how

考虑一下6 3 1 5。

• #"+&1展开为1的横向条形图:1 1 1 0 0 0 1 0 0 0 1 1 1 0
• |.@|:按规则旋转:1 0 0 0 1 0 0 1 1 0 1 1 1 0 1 1 1
• [:(0-.~#;._1@,~&0)"1对每一行的运行数:1 0 1 1 1 2 1 1 1 4 0
• |:转座:1 1 1 2 2 4 0 1 1 1 0
• [:(~....I.@~:)"1对于每一行，得到节点(uniq)和节点筛位置(即，每个行的第一次出现的位置)。如行1: 1 1 1 2 2 4-行1 1 2 4- Uniq 0 3 5-第一次出现的位置
• #-从长度减去位置:0 3 5-第一次出现的位置6 3 1-长度减去位置
• *将这些值乘以uniq值:给出最大矩形的大小。(记住，即使有多重，我们仍然只显示1行)1 2 4- Uniq 6 3 1-长度减去位置
• 0<./@-.~[:,扁平化，移除零，取最小。4.

Answer 2

Wolfram语言(数学)，56字节

Min[(aTr/@Pick[a+0(l=SplitBy[#,#<a&]),Min/@l,a])/@#]&

在网上试试！

Answer 3

05AB1E，24 字节数

@JonahJ回答港：

Å1ζRεÅγsÏ}ζεDÙþ©kygα®*}ß

在网上试试或验证所有测试用例.

@Neil木炭回答的端口也是24 字节数：

0.øŒʒD¦¨ß‹Á2£P}妨Wsg*}ß

在网上试试或验证所有测试用例.

Explanation:

Å1                # Map each value in the (implicit) input-list to a list of that
                  # many 1s
  ζ               # Zip/transpose; swapping rows/columns,
                  # using a space as filler by default for rows of unequal length
   R              # Reverse the rows
    ε             # Map over each row:
     Åγ           #  Run-length encode it, pushing a list of values and lengths
                  #  separated to the stack
       s          #  Swap so the values are at the top
        Ï         #  Only leave the lengths at truthy (==1) positions
    }ζ            # After the map: zip/transpose with space filler again
      ε           # Map over each row:
       D          #  Duplicate the current list
        Ù         #  Uniquify the items in the copy
         þ        #  Remove all spaces by only keeping digits
          ©       #  Store this in variable `®` (without popping)
           k      #  Get the first 0-based index of each unique value in the list
              α   #  Calculate the absolute difference of each index with
            yg    #  the length of the current row-list
               ®* #  Multiply the values to list `®` at the same positions 
      }ß          # After the map: pop and push the flattened minimum
                  # (which is output implicitly as result)

0.ø               # Surround the (implicit) input-list with leading/trailing 0
   Π             # Pop and push all sublists
ʒ                 # Filter this list of lists by:
 D                #  Duplicate the sublist
  ¦¨              #  Remove the first and last items in the copy
    ß             #  Pop and push the minimum
     ‹            #  Check for each value in the list if this minimum is larger
      Á           #  Rotate the list of checks once towards the right
       2£         #  Pop and leave just the first two
         P        #  Product to check if both of them are truthy
}ε                # After the filter: map over the remaining sublists:
  ¦¨              #  Remove the first and last items again
    W             #  Push the minimum (without popping the list)
                  #  (this will be an empty string for empty lists)
     s            #  Swap so the list is at the top
      g           #  Pop and push its length
       *          #  Multiply the length by this minimum
 }ß               # After the map: pop and push the minimum integer (ignoring any
                  # empty strings)
                  # (which is output implicitly as result)