[已解决]求最大矩形面积

Stubborn · 发表于 2019-11-19 17:10:01

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

本帖最后由 Stubborn 于 2019-12-2 05:28 编辑

给定 n 个非负整数，用来表示`柱子`的高度。每个柱子彼此相邻，且宽度为 1

输入: [2,1,5,6,2,3]
输出: 10

有大的数组[x for x in rang(20000) ] ,所以尽可能的吧时间复杂度降低到 O(n^2)以下

图解：

代码实现：

class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
if len(heights) == 1: return heights[0]
heights.append(0)
stack = [0, ]
length = len(heights)
result = 0
for h in range(1, length):
if heights[stack[-1]] < heights[h]:
stack.append(h)
else:
while heights[stack[-1]] >= heights[h]:
s = stack.pop()
if not stack:
S = h * heights[s]
if S > result: result = S
stack.append(h)
break
S = (h - stack[-1] - 1) * heights[s]
if S > result: result = S
if heights[stack[-1]] < heights[h]:
stack.append(h)
break
return result

复制代码

最佳答案

月排行榜 / 总排行榜

__mrsq__

2019-11-21 14:24:29

class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
res=0
numdict = []
for i in heights:
if numdict==[]:
numdict.append(i)
elif i >= numdict[-1]:
numdict.append(i)
else:
t = 0
for l in range(len(numdict)-1,-1,-1):
if numdict[l]>i:
t=t+1
res=max(res,numdict[l]*t)
else:
break
numdict = numdict[:-t]+(t+1)*[i]
for i in set(numdict):
res =max(res,i*(len(numdict)-numdict.index(i)))
return res

复制代码

写了一个通过边缘的.....

跳转到最佳答案楼层

wp231957 · 发表于 2019-11-19 18:43:35

咋净研究算法，狠♂呀

阴阳神万物主 · 发表于 2019-11-20 18:08:42

本帖最后由阴阳神万物主于 2019-11-20 18:14 编辑

真好玩儿^_^

from typing import List
def MaxRectangle(heights:List[int]) -> int:
m_area = 0
for h in range(max(heights),0,-1):
area = 0
for each in heights:
if each < h:
m_area = max(area,m_area)
area = 0
else:
area += h
return m_area

复制代码

小小地改动一下：

from typing import List
def MaxRectangle(heights:List[int]) -> int:
m_area = len(heights)
for h in range(max(heights),1,-1):
area = 0
for each in heights:
if each < h:
m_area = max(area,m_area)
area = 0
else:
area += h
return m_area

复制代码

danteer · 发表于 2019-11-20 18:59:46

本帖最后由 danteer 于 2019-11-20 19:08 编辑

def func(list1):
result = []
for i in range(min(list1),max(list1)+1):
indexlist = []
for each in range(len(list1)):
if list1[each] == i:
indexlist.append(each)
right = -1
for each in indexlist:
if each <= right:
continue
left = each - 1
right = each + 1
while left > -1:
if list1[left] >= list1[each]:
left -= 1
else:
left += 1
break
if left == -1:
left = 0
while right < len(list1):
if list1[right] >= list1[each]:
right += 1
else:
right -= 1
break
if right == len(list1):
right -= 1
result.append(list1[each]*(right-left+1))
return max(result)

复制代码

Stubborn · 发表于 2019-11-20 19:52:15

danteer 发表于 2019-11-20 18:59

[0,0,0,0,0,0,0,0,2147483647]

复制代码

超时了~

Stubborn · 发表于 2019-11-20 19:54:03

阴阳神万物主发表于 2019-11-20 18:08
真好玩儿^_^

小小地改动一下：

数组会出现 0 表示没有高度，宽度为1，原来的题目也没有说，测试才发现，会分治嘛，教教我呀

阴阳神万物主 · 发表于 2019-11-20 19:56:41

本帖最后由阴阳神万物主于 2019-11-20 20:03 编辑

Stubborn 发表于 2019-11-20 19:54
数组会出现 0 表示没有高度，宽度为1，原来的题目也没有说，测试才发现，会分治嘛，教教我呀

啊哈，我没系统地学过算法。
我也并没有考虑有高度为 0 的情况，我想的是高度至少为1 …… 如果说真的碰上那样的数据，算瞎猫碰着死耗子了。
根据矩形的面积公式，有一边长度为零，那么面积应该为 0 啊。

Stubborn · 发表于 2019-11-20 20:03:31

阴阳神万物主发表于 2019-11-20 19:56
啊哈，我没系统地学过算法。

决定最大矩形的面积，总是最小值决定的。代码还没有写出来

#  [2,1,5,6,2,3] -> 6 * 1 = 6
# [2] -> 2       [5,6,2,3] -> 2*4 = 8
#             [5,6]->2*5 =  10  [3]-> 3
#             5,6 -> 5，6

阴阳神万物主 · 发表于 2019-11-20 20:06:24

Stubborn 发表于 2019-11-20 20:03
决定最大矩形的面积，总是最小值决定的。代码还没有写出来

# [2,1,5,6,2,3] -> 6 * 1 = 6
...

感觉跟短板效应有点儿像啊。

阴阳神万物主 · 发表于 2019-11-20 20:07:34

本帖最后由阴阳神万物主于 2019-11-20 20:11 编辑

Stubborn 发表于 2019-11-20 20:03
决定最大矩形的面积，总是最小值决定的。代码还没有写出来

# [2,1,5,6,2,3] -> 6 * 1 = 6
...

既然是这样，那可就更好办了

from typing import List
def MaxRectangle(heights:List[int]) -> int:
m_area = 0
le = len(heights)
for l in range(le):
for r in range(l+1,le+1):
m_area = max(m_area,min(heights[l:r])*(r-l))
return m_area

复制代码

Stubborn · 发表于 2019-11-20 20:14:32

阴阳神万物主发表于 2019-11-20 20:07
既然是这样，那可就更好办了

数组太长，超时了~ GO

danteer · 发表于 2019-11-20 20:16:57

Stubborn 发表于 2019-11-20 19:52
超时了~

def func(list1):
result = []
for i in set(list1):
indexlist = []
for each in range(len(list1)):
if list1[each] == i:
indexlist.append(each)
right = -1
for each in indexlist:
if each <= right:
continue
left = each - 1
right = each + 1
while left > -1:
if list1[left] >= list1[each]:
left -= 1
else:
left += 1
break
if left == -1:
left = 0
while right < len(list1):
if list1[right] >= list1[each]:
right += 1
else:
right -= 1
break
if right == len(list1):
right -= 1
result.append(list1[each]*(right-left+1))
return max(result)

复制代码

换个set就能继续暴力破解了，不过dp还是不会弄

阴阳神万物主 · 发表于 2019-11-20 20:21:19

Stubborn 发表于 2019-11-20 20:14
数组太长，超时了~ GO

也就是我一开始那个可以是吧？

danteer · 发表于 2019-11-20 20:22:26

本帖最后由 danteer 于 2019-11-20 20:28 编辑

def func(heights):
result = []
for i in set(heights):
indexlist = []
for each in range(len(heights)):
if heights[each] == i:
indexlist.append(each)
right = -1
for each in indexlist:
if each <= right:
continue
left = each - 1
right = each + 1
while left > -1:
if heights[left] >= heights[each]:
left -= 1
else:
left += 1
break
if left == -1:
left = 0
while right < len(heights):
if heights[right] >= heights[each]:
right += 1
else:
right -= 1
break
if right == len(heights):
right -= 1
result.append(heights[each]*(right-left+1))
return max(result)

复制代码

阴阳神万物主 · 发表于 2019-11-20 20:28:04

Stubborn 发表于 2019-11-20 20:14
数组太长，超时了~ GO

咱一开始那个，时间复杂度为 O(n) ，后来这个是 O((n^2)!) 可不是天壤之别吗，只是看着简单而已

Stubborn · 发表于 2019-11-20 20:37:59

阴阳神万物主发表于 2019-11-20 20:28
咱一开始那个，时间复杂度为 O(n) ，后来这个是 O((n^2)!) 可不是天壤之别吗，只是看着简单而已

处理下数组出现0的情况，0 表示没有高度等于0，宽度为1

Stubborn · 发表于 2019-11-20 20:41:18

danteer 发表于 2019-11-20 20:22

超时了，数组长度很长的时候，需要数据吗？原题链接

danteer · 发表于 2019-11-20 20:50:18

Stubborn 发表于 2019-11-20 20:41
超时了，数组长度很长的时候，需要数据吗？原题链接

看到了，1到19999

Stubborn · 发表于 2019-11-20 21:16:40

danteer 发表于 2019-11-20 20:50
看到了，1到19999

这个用分治

阴阳神万物主 · 发表于 2019-11-20 21:42:39

Stubborn 发表于 2019-11-20 20:37
处理下数组出现0的情况，0 表示没有高度等于0，宽度为1

好家伙，你看这样行不？

from typing import List
def MaxRectangle(heights:List[int]) -> int:
m_area = 0
for h in range(max(heights),0,-1):
area = 0
for each in heights:
if each < h:
m_area = max(area,m_area)
area = 0
else:
area += h
m_area = max(area,m_area)
return m_area
if __name__ == '__main__':
print('10 输出',MaxRectangle([2,1,5,6,2,3]))
print('0 输出',MaxRectangle([0,0,0,0]))
print('1 输出',MaxRectangle([0,0,0,1]))

复制代码

账号		自动登录	找回密码
密码			立即注册

[已解决]求最大矩形面积

马上注册，结交更多好友，享用更多功能^_^

评分

评分