leetcode：84. 柱状图中最大的矩形（java）

今天药忘吃喽~ 2021-09-28 08:54 440阅读 0赞

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。

图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。

示例:

输入: [2,1,5,6,2,3]
输出: 10
public int largestRectangleArea(int[] heights) {
    int max = 0;
    for (int i = 0; i < heights.length; i++) {
        int mid = 0;
        int left = 0;
        int right = 0;
        mid = i;
        left = i - 1;
        right = i + 1;
        int wide = 1;
        while (left >= 0 && heights[left] >= heights[mid]) {
            wide++;
            left--;
        }
        while (right < heights.length && heights[right] >= heights[mid]) {
            wide++;
            right++;
        }
        int area = 0;
        area = wide * heights[mid];
        if (area > max) {
            max = area;
        }
    }
    return max;
}