代码随想录算法训练营第六十天|84.柱状图中最大的矩形

2024-01-08 13:19:41

代码随想录 (programmercarl.com)

84.柱状图中最大的矩形

方法一:暴力解法

寻找每个柱子左边和右边第一个比他矮的,确定宽度,高度,最终得出面积

超时了,时间复杂度是O(n^2)。

方法二:双指针法

时间复杂度是O(n)

方法三:单调栈法

寻找元素第一个比他大或比他小的元素,都可以使用单调栈的思路

接雨水求的是右边第一个比他大的元素====递增的单调栈

而本题求的是右边第一个比他小的元素====递减的单调栈

注意:需要在 height数组前后各加一个元素0

left:表示矩形左边第一个比他小的数字;right:表示矩形右边第一个比他小的数组

矩形面积s = (right - left - 1) * w;

class Solution {
    public int largestRectangleArea(int[] heights) {
        int[] newHeight = new int[heights.length + 2];
        System.arraycopy(heights, 0, newHeight, 1, heights.length);
        //该函数意义:public static void arraycopy(Object src,
        //                             int srcPos,
        //                             Object dest,
        //                             int destPos,
        //                             int length)
        //src:源数组;	srcPos:源数组要复制的起始位置;
        //dest:目的数组;	destPos:目的数组放置的起始位置;	length:复制的长度。
        //注意:src and dest都必须是同类型或者可以进行转换类型的数组.
        newHeight[heights.length + 1] = 0;
        newHeight[0] = 0;
        //给原数组首尾加0
        int res = 0;

        Stack<Integer> stack = new Stack<>();
        stack.push(0);

        for (int i = 1; i < newHeight.length; i++) {
            while (newHeight[i] < newHeight[stack.peek()]){
                //因为首尾加了0,所以栈不可能为空,省略判断
                int mid = stack.peek();
                stack.pop();
                int h = newHeight[mid];
                int left = stack.peek();
                int right = i;
                int w = right - left - 1;
                res = Math.max(res, h * w);
            }
            stack.push(i);
        }
        return res;
    }
}

文章来源:https://blog.csdn.net/YOYU_/article/details/135428734
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。