原题链接

leetcode web address

题目概述

在一个直方图中, 找到最大的矩形.

解题思路

我一开始想到的解题方法是通过分治的方法进行排序.方法如下,首先找到最小的数字,那么这个最小高度的矩形可以算出,然后分别计算它的左边的部分,和右边的部分,三者之间取最大值.
这种方法的算法复杂度是O(nlogn),极端情况是O(n²).
然后挂了,再参考别人的思路后终于写了出来QAQ.
正确的解题方法是构造一个递增的栈,每当有新的数据进来时.进行比较,如果比栈顶小的话,就出栈算面积.
值得注意的地方有两个:
1, 就是低高低的情况,所以矩形的长度还要向前计算.所以矩形宽度还要看前一个的索引.如果已经是第一个就要全部计算在内.
2,就是连续相同高度的情况,如果出现这种情况解决方法有2,一个是让其进栈,一个是永远只取最后一个值进行计算.
为了便于计算我在这个序列的尾巴增加了一个0高度.

代码

func largestRectangleArea(heights []int) int {
    var result int
    result = 0
    tmpResult := 0

    heights = append(heights, 0)
    heightIndex := make([]int, 0)

    tmpValue := 0
    tmpIndex := 0

    for index, value := range heights {
        for {
            if len(heightIndex) == 0 || value >= heights[heightIndex[len(heightIndex) - 1]] {
                heightIndex = append(heightIndex, index)
                break
            } else {
                if len(heightIndex) == 1 {
                    tmpIndex = -1
                } else {
                    tmpIndex = heightIndex[len(heightIndex) - 2]
                }
                tmpValue = heights[heightIndex[len(heightIndex) - 1]]
                tmpResult = (index - tmpIndex - 1) * tmpValue
                if result < tmpResult {
                    result = tmpResult
                }

                heightIndex = heightIndex[:len(heightIndex) - 1]
            }
        }
    }
    return result
}