084 Largest Rectangle in Histogram 柱状图中最大的矩形

给出 n 个非负整数来表示柱状图的各个柱子的高度，每个柱子紧挨彼此，且宽度为 1 。
您的函数要能够求出该柱状图中，能勾勒出来的最大矩形的面积。

详见：https://leetcode.com/problems/largest-rectangle-in-histogram/description/

Java实现：

方法一：遍历数组，每找到一个局部峰值，就向前遍历所有的值，算出共同的矩形面积，每次对比保留最大值。

class Solution {

    public int largestRectangleArea(int[] heights) {

        int res=0;

        int n=heights.length;

        for(int i=0;i<n;++i){

            if(i+1<n&&heights[i]<=heights[i+1]){

                continue;

            }

            int minH=heights[i];

            for(int j=i;j>=0;--j){

                minH=Math.min(minH,heights[j]);

                int area=minH*(i-j+1);

                res=Math.max(res,area);

            }

        }

        return res;

    }

}

方法二：

class Solution {

    public int largestRectangleArea(int[] heights) {

        int n=heights.length;

        if (heights == null || n == 0){

            return 0;

        }

        int res=0;

        Stack<Integer> stack = new Stack<Integer>();

        for (int i = 0; i < n; ++i) {

            //如果高度递增，那么一次入栈。

            if (stack.isEmpty() || heights[stack.peek()] <= heights[i]) {

                stack.push(i);

            }

            //如果当前柱比栈顶的低，那么把栈顶的拿出来，计算所有已经出栈的最大面积。

            else {

                int start = stack.pop();

                int width = stack.isEmpty() ? i : i - stack.peek() - 1;

                res = Math.max(res, heights[start] * width);

                --i;

            }

        }

        //循环过后栈中是递增的条目，计算在栈中递增条目的最大面积。

        while (!stack.isEmpty()) {

            int start = stack.pop();

            int width = stack.isEmpty() ? n : n - stack.peek() - 1;

            res = Math.max(res, heights[start] * width);

        }

        return res;

    }

}

参考：https://www.cnblogs.com/grandyang/p/4322653.html

巴特西

084 Largest Rectangle in Histogram 柱状图中最大的矩形

最新文章

热门文章