天际线上最大的矩形

Question

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

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

您的任务是查找天际线中最大矩形的区域。在这种情况下，最大的矩形区域为12。下面是突出显示的矩形：

    #
  # #
 ## ###
 RRRRRR
#RRRRRR

您可以假设输入至少包含一个建筑物(数组的长度>0)。这是密码-高尔夫，你知道该怎么做。

灵感来自这困惑-SE贴子。

测试用例

[1] -> 1
[2, 2] -> 4
[3, 2, 1] -> 4
[1, 2, 3] -> 4
[1, 5, 1, 5] -> 5
[1, 4, 1, 4, 1] -> 5
[1, 4, 5, 4, 1] -> 12
[1, 5, 4, 5, 1] -> 12
[1, 2, 3, 5, 1, 3] -> 6
[1, 3, 3, 1, 4, 5, 2] -> 8
[1, 3, 3, 1, 1, 1, 1] -> 7

Answer 1

八度，50字节

@(a)max(([c,v]=runlength([(a<=a').*a;0*a](:))).*v)

在网上试试！

基于我对PARI/GP的回答，但更有趣。这值得写约拿式的解释。

how

以a = [1,3,4,2,5,3,3]为例。

• a<=a'创建一个矩阵，其中(i,j)处的条目为a[j]<=a[i]：1 0 0 0 1 1 0 1 1 1 0 1 1 0 0 1 1 0 0 1 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 0 1 0 0 1 1 1 0 0 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1 1 0 0 1 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
• .*a将矩阵的i-th列乘以a[i]：1 0 0 0 1 3 3 0 4 2 0 3 3 3 1 0 0 0 1 3 3 1 0 0 0 3 4 0 0 0 3 4 0 0 0 3 4 0 0 0 3 4 0 0 0 3 4 0 0 0 3 4 0 0 0 1 4 0 0 0 3 3 1 0 0 0 3 3 3 0 0 0 3 3 1 0 0 0 3 3 1 0 0 0 3 3 1 0 0 0 3 3 1 0 0 0 3 3 1 0 0 0 3 3 3 0 0 0 3 3 1 0 0 0 3 3 3 0 0 0 3 3 3 0 0 0
• [...;0*a]在矩阵中附加一行零，以便在获取行长编码时分隔列:1 0 0 0 1 3 3 3 4 2 0 3 3 1 0 0 2 0 0 1 3 1 0 0 2 0 0 1 4 0 0 0 3 1 0 0 0
• ...(:)将矩阵串联成列向量(实际输出是下一行向量的转置)：1 1 1 0 3 3 3 0 0 0 4 0 4 0 0 0 2 2 2 0 0 0 5 0 0 0 3 3 3 0 3 0 3 00 3 3 0 3 3 3
• [c,v]=runlength给出了游程长度编码，其中每次非零行对应于天际线中的一个矩形:C=7 2 2 1 3 3 3 1 1 1 4 6 4 1 4 2 2 2 1 3 1 v=1 0 3 0 3 0 4 0 4 0 5 0 3 0 3 0 3 0 3 0 0
• ([c,v]=runlength(...)).*v将c和v元素乘以元素，给出每次运行的“面积”：7 0 6 0 9 0 4 0 4 0 12 0 5 0 0 0 9 0 6 0 9 9 0 9 0 0
• 最后，max找到结果的最大值: 12

Answer 2

Wolfram语言(数学)，35字节

-5字节，因为@att。

Max[Tr[Min@#+0#]&/@Subsequences@#]&

在网上试试！

Answer 3

05AB1E，8 字节数

ŒεWsg*}à

@UnrelatedString果冻回答港，所以一定要支持他/她！

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

解释：

Π      # Get all sublists of the (implicit) input-list
 ε      # Map each sublist to:
  W     #  Push its minimum (without popping the sublist)
   s    #  Swap so the sublist is at the top again
    g   #  Pop and push its length
     *  #  Multiply it by the minimum
 }à     # After the map: pop and push the maximum
        # (after which it is output implicitly as result)