给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。
求在该柱状图中,能够勾勒出来的矩形的最大面积。
固定高度,往两边扩张
class Solution { public int largestRectangleArea(int[] heights) { if (heights == null || heights.length == 0) return 0; int max = 0, n = heights.length; for (int i = 0; i < n; ++i) { int l = i, r = i; while (l >= 0 && heights[l] >= heights[i]) --l; while (r < n && heights[r] >= heights[i]) ++r; max = Math.max(max, heights[i] * (r - l - 1)); } return max; } }