题目

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

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

示例 1:

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

示例 2：

输入： heights = [2,4]
输出： 4

提示：

• 1 <= heights.length <=10⁵
• 0 <= heights[i] <= 10⁴

题解

public int largestRectangleArea(int[] heights) {
    // 考虑使用二分法
    BiFunction<Integer, Integer, Integer> divide = new BiFunction<Integer, Integer, Integer>() {
        @Override
        public Integer apply(Integer left, Integer right) {
            // 超过区间
            if (left > right) {
                return 0;
            }
            // 找到当前区间最小值索引
            int mid = left;
            for (int i = left + 1; i <= right; i++) {
                if (heights[i] < heights[mid]) {
                    mid = i;
                }
            }

            return
                Math.max(
                    // 计算当前区间最大面积
                    (right - left + 1) * heights[mid],
                    // 计算左右两边最大面积
                    Math.max(
                        this.apply(left, mid - 1),
                        this.apply(mid + 1, right)
                    )
                );
        }
    };

    int length = heights.length;

    return length == 0 ? 0 : divide.apply(0, length - 1);
}