华为软件机考826第二题思路

华为笔试第二道题目考察的是单调栈，奈何笔试紧张的一塌糊涂没写出来，冷静下来写写思路，希望下次在遇到类似的题目可以写出来~如果代码有问题欢迎指正呀.

题目：
一个仓库摆放了一排连续整齐的长宽不等的矩形箱子，现在要在这些高低不等的箱子
组成的柱状图中找到最大的一块完整矩形面积来张贴一张海报。简而言之，求最大矩形。

输入：egg：[1,1,1,1,2,1,1],[5,2,5,4,5,1,6]
输出：16

同类型题目：leetcode84

我的思路为首先把输入进行处理，生长一个每个宽度为1，高度为对应高的数组，然后再利用单调栈的思路求解。单调栈思路：

从左向右遍历，当当前位置i的高度小于前一高度的话，说明右边界为i-1，左边界为弹出stack中最后一个数后的索引值，计算当前最大面积，直到不满足小于时候，栈内压入索引i。

#输入处理
in_str = input()
#处理左括号 右括号以及分割
id =[]
for i in range(len(in_str)):
    if in_str[i] in ['[', ']']:
        id.append(i)
in_str = in_str.replace('[','')
in_str = in_str.replace(']','')
nums = [int(str_num) for str_num in in_str.split(',')]
#函数定义
def create_nums(nums):
    ws, hs = nums[:len(nums)//2], nums[len(nums)//2:]
    new_hs = []
    for i in range(len(ws)):
        new_hs += [hs[i]]*ws[i]
    return new_hs
def max_area(height):
    stack = [-1]
    res = 0
    height = height+[0]
    for i in range(len(height)):
        while len(stack)>1 and height[i]<height[stack[-1]]:
            res = max(res, height[stack.pop()]*(i-1-stack[-1]))
        stack.append(i)
    return res
#调用函数
def main():
    if min(nums)<=0 or len(nums)&1==1 or id[1]-id[0]!=id[3]-id[2]:
        return 0
    else:
        hs = create_nums(nums)
        res = max_area(hs)
        return res
print(main())