首页>itarticle>【leetcode84】largest rectangle in histogram 最大面积覆盖的矩阵
【leetcode84】largest rectangle in histogram 最大面积覆盖的矩阵
admin1月 23, 20210
“The Linux philosophy is “Laugh in the face of danger”.Oops.Wrong One. “Do it yourself”. Yes, that”s it.” Linux的哲学就是“在危险面前放声大笑”,呵呵,不是这句,应该是“一切靠自己,自力更生”才对。
* 给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。 * 求在该柱状图中,能够勾勒出来的矩形的最大面积。 * * 从中间向两端发散计算 */ publicclass{ publicintlargestRectangleArea(int[] heights){ int max = 0; for (int i = 0; i < heights.length; ++i) { int index = heights[i]; int l = i, r = i; while (l >= 0 && heights[l] >= index) --l; while (r < heights.length && heights[r] >= index) ++r; int area = heights[i] * (r - l + 1-2); max = Math.max(area, max); } return max; }
近期评论