题解 | #直方图内最大矩形#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param heights int整型一维数组 
     * @return int整型
     */
    public int countArea(int[] heights, int N, int i) {
        int le = i, ri = i;
        while(le > -1 && heights[le] >= heights[i]) le--;
        while(ri < N  && heights[ri] >= heights[i]) ri++;
        return (ri - le - 1) * heights[i];
    }
    public int largestRectangleArea (int[] heights) {
        // write code here
        if(heights == null) {
            return 0;
        }
        int N = heights.length;
        if(N == 0) {
            return 0;
        } else if(N == 1) {
            return heights[0];
        }
        int pre = heights[0];
        int maxArea = countArea(heights, N, 0);
        for(int i = 1; i < N; i++) {
            if(heights[i] == pre) {
                continue;
            }
            pre = heights[i];
            int area = countArea(heights, N, i);
            if(area > maxArea) {
                maxArea = area;
            }
        }
        return maxArea;
    }
}