当前位置 博文首页 > Inmaturity_7的博客：算法练习帖--42--柱状图中最大的矩形(Java)
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
（题目来源：力扣官网）
求在该柱状图中，能够勾勒出来的矩形的最大面积。
以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。
示例:
输入: [2,1,5,6,2,3]
输出: 10
package com.lxf.test;
public class LargestRectangleArea {
public static void main(String[] args) {
System.out.println(largestRectangleArea(new int[]{2,1,2}));
}
public static int largestRectangleArea(int[] heights) {
int maxArea=0;
//遍历数组的每一个值
for (int i = 0; i < heights.length; i++) {
int curArea=heights[i];
int j=i;
int k=i;
//当前数字向右搜索比它大的最后一个数字的下标
while(j<heights.length&&curArea<=heights[j]){
j++;
}
//当前数字向左搜索比它大的最后一个数字的下标
while(k>=0&&curArea<=heights[k]){
k--;
}
//两下标相减再减1乘以当前数字就是矩形的面积了，记录每个面积的最大值
maxArea=Math.max(maxArea, (j-k-1)*heights[i]);
}
return maxArea;
}
}
public class LargestRectangleArea {
public static void main(String[] args) {
System.out.println(largestRectangleArea(new int[]{2,1,2}));
}
public static int largestRectangleArea(int[] heights) {
int maxArea=0;
//遍历数组的每一个值
for (int i = 0; i < heights.length; i++) {
int curArea=heights[i];
int j=i;
int k=i;
//当前数字向右搜索比它大的最后一个数字的下标
while(j<heights.length&&curArea<=heights[j]){
j++;
}
//当前数字向左搜索比它大的最后一个数字的下标
while(k>=0&&curArea<=heights[k]){
k--;
}
//两下标相减再减1乘以当前数字就是矩形的面积了，记录每个面积的最大值
if(heights[i]!=(j-k-1)){//排除正方形
maxArea=Math.max(maxArea, (j-k-1)*heights[i]);
}
}
return maxArea;
}
}
