35（牛客Top100）-84.柱状图中最大的矩形

本文主要是介绍35（牛客Top100）-84.柱状图中最大的矩形，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
思路：
方法1：栈 + 邵兵

    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        if (len == 0) return 0;
        if (len == 1) return heights[0];

        int area = 0;
        //新建一个数组，加头尾两个节点，作为两个邵兵
        int[] newHeights = new int[len + 2];
        //1.将数组赋值给有头尾邵兵的新数组
        for (int i = 0; i < len; i++) {
            newHeights[i + 1] = heights[i];
        }
        //数组长度和变量重置
        len += 2;
        heights = newHeights;
        Deque<Integer> stack = new ArrayDeque<>();
        stack.addLast(0);
        for (int i = 1; i < len; i++) {
            while (heights[stack.peekLast()] > heights[i]) {
                int height = heights[stack.removeLast()];
                int width =i - stack.peekLast() - 1;
                area = Math.max(area, width * height);
            }
            stack.addLast(i);
        }
        return area;
    }

时间复杂度：O(N)
空间复杂度：O(N)

这篇关于35（牛客Top100）-84.柱状图中最大的矩形的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！