Largest Rectangular Area in a Histogram 最大连续面积

在HankerRank遇到一题计算柱状图连续矩形面积的问题.

举例 hist = [3, 2, 3]. 在这个柱状图里面最大可以容纳一个high = 2 length = 3的连续矩形, 其面积 = 2*3 = 6.

按照提示需要使用stack来是时间复杂度保持在O(n). 搜索提示和代码, 把自己的理解描述如下:

加入数组是升序的 hist = [1, 2, 3]

因为数组是升序的, 所以每一个都会和之后的 high 形成更大的连续面积.

也因为数组是升序的, 所以每一个都会和之前的 high 无法形成更大的连续面积. 3和2无法形成, 因为2和3 已经组合.

所以升序的计算最好是在数组的最后面, i = 3时

i = 3 计算 index = 2的面积. area = 3 * 1; h[index] * (i - (index - 1) - 1)

i = 3 计算 index = 1的面积. area = 2 * 2; h[index] * (i - (index - 1) - 1)

i = 3 计算 index = 0的面积. area = 1 * 3; h[index] * i
加入数组是降序的 hist = [3, 2, 1]

和上面分析相反, 但是在i+1均可计算前一个连续矩形面积.

i = 0 不计算

i = 1 计算 index = 0 的面积. area = 3 * 1; h[index] * i

i = 2 计算 index = 1 的面积. area = 2 * 2; h[index] * i

i = 3 计算 index = 2 的面积. area = 1 * 3; h[index] * i



public static long GetLargestArea(int[] h)

{

        long maxarea = -1;

        long toparea = -1;

        int i = 0;

        int top;

        var stack = new Stack<int>();

        while(i < h.Length)

        {

            if(stack.Count == 0 || h[i] >= h[stack.Peek()])

            {

                // 把升序的数组索引入栈.

                stack.Push(i++);

            }

            else

            {

                // 把降序的数组索引出栈.并计算其面积.

                top = stack.Pop();

                toparea = h[top] * (stack.Count == 0 ? i : (i - stack.Peek() - 1));

                if(toparea > maxarea)

                    maxarea = toparea;

            }

        }

        while(stack.Count != 0)

        {

            top = stack.Pop();

            toparea = h[top] * (stack.Count == 0 ? i : (i - stack.Peek() - 1));

            if(toparea > maxarea)

                maxarea = toparea;

        }

        return maxarea;

}

参考:

Largest Rectangular Area in a Histogram

Hackerrank

巴特西

Largest Rectangular Area in a Histogram 最大连续面积

最新文章

热门文章