题目

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

histogram.png

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

histogram_area.png

图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。
链接：https://leetcode-cn.com/problems/largest-rectangle-in-histogram

思考1 - 双指针法

• 每个柱子限制其面积的为左右比其矮的柱子，所以找到左右小于其高度的柱子下标，作差求得面积宽，再乘以当前柱子高度即可。
• 循环比较每个柱子的面积，得出最大值返回。

解法1

class Solution {
    public int largestRectangleArea(int[] heights) {
        int result = 0;
        for (int i = 0; i < heights.length; i++){
            int left = i;
            int right = i;
            int value = heights[i];
            while (left >= 0){
                if (heights[left] < value){
                    break;
                }
                left --;
            }
            while (right < heights.length){
                if (heights[right] < value){
                    break;
                }
                right ++;
            }
            int res = (right - left -1) * value;
            if (res > result){
                result = res;
            }
        }
        return result;
    }
}