#yyds干货盘点# 名企真题专题：直方图内最大矩形

elegant lv.1

发布时间：2023-01-03 16:14:38 266

相关标签： # java# java# 数据

1.简述：

描述

给定一个数组heights，长度为n，height[i]是在第i点的高度，那么height[i]表示的直方图，能够形成的最大矩形是多少?

1.每个直方图宽度都为1

2.直方图都是相邻的

3.如果不能形成矩形，返回0即可

4.保证返回的结果不会超过231-1

数据范围:

如输入[3,4,7,8,1,2]，那么如下:

#yyds干货盘点# 名企真题专题：直方图内最大矩形_直方图_03

示例1

输入：

[3,4,7,8,1,2]

返回值：

示例2

输入：

[1,7,3,2,4,5,8,2,7]

返回值：

2.代码实现：

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param heights int整型一维数组 
     * @return int整型
     */
    public int largestRectangleArea (int[] heights) {
        //总宽度
        int n=heights.length;
        //新建单调栈
        ArrayDeque stack=new ArrayDeque<>();
        
        int res=0;
        for(int i=0;i<n;i++){
            //只要栈顶元素比当前大，则可以统计以栈顶元素为高的最大面积
            while(!stack.isEmpty()&&heights[stack.peek()]>heights[i]){
                //由于单调栈内元素是单调不递减的，L到i-1之间的高度一定大于等于curHeight
                int curHeight=heights[stack.pop()];
                //如果栈中元素为空，说明0到i-1之间的高度均大于等于curHeight
                int L=stack.isEmpty()?0:stack.peek()+1;
                res=Math.max(res,(i-L)*curHeight);
            }
            stack.push(i);
        }
        
        //如果遍历完之后，单调栈还不为空，则继续统计可能的最大面积
        while(!stack.isEmpty()){
            int curHeight=heights[stack.pop()];
            int L=stack.isEmpty()?0:stack.peek()+1;
            res=Math.max(res,(n-L)*curHeight);
        }
        
        return res;
    }
}

文章来源： https://blog.51cto.com/u_15488507/5974505

特别声明：以上内容（图片及文字）均为互联网收集或者用户上传发布，本站仅提供信息存储服务！如有侵权或有涉及法律问题请联系我们。