给出n个数字,代表直方图的条高,直方图每一条的宽度为1,请计算直方图中最大矩形的面积
上图是每条宽度为1, 高度 =[2,1,5,6,2,3].的直方图
图中的阴影部分是该直方图中面积最大的矩形,面积为10个单位
例如:
给出的高度 =[2,1,5,6,2,3],
返回10.
给出的高度 =[2,1,5,6,2,3],
返回10.
//类似于中心拓展法,针对每个位置,找到前后大于等于该高度元素的数量 public class Solution { /** * * @param height int整型一维数组 * @return int整型 */ public int largestRectangleArea (int[] height) { // write code here int max=0; int l=height.length; for(int i=0;i<l;i++){ int low=i; int high=i; int sum=-1; while(low>=0 && height[low]>=height[i]){ sum++; low--; } while(high<l && height[high]>=height[i]){ sum++; high++; } max=Math.max(max,sum*height[i]); } return max; } }
public class Solution { public int largestRectangleArea(int[] height) { if(height==null) return 0; int i,j,S=0; for(i=0;i<height.length;i++){ int minheight=Integer.MAX_VALUE; for(j=i;j<height.length;j++){ minheight=Math.min(minheight,height[j]); S=Math.max(S,(j-i+1)*minheight); } } return S; } }
以每个直方条为中心, 向两边延展. 遇到更小的直方条便停止. 效率太低了..O(n2). TAT
public class Solution { public int largestRectangleArea(int[] height) { int len = height.length; int maxArea = 0; int tmp = 0; // 以每个直方条为中心, 向两边延展 for (int i = 0; i < len; i++) { int j = i; int k = i; // 向右延展, 遇到小于当前的停止 for (; j < len; j++) { if (height[i] > height[j]) { break; } } // 向左延展, 遇到小于当前的停止 for (; k >= 0; k--) { if (height[i] > height[k]) { break; } } // 计算面积 tmp = height[i] * (j - k - 1); if (tmp > maxArea) { maxArea = tmp; } } return maxArea; } }
参考其他, O(n)
import java.util.Stack; /* 用堆栈计算每一块板能延伸到的左右边界 对每一块板 堆栈顶矮,这一块左边界确定,入栈 堆栈顶高,堆栈顶右边界确定,出栈,计算面积 入栈时左边界确定 出栈时右边界确定 堆栈里元素是递增的 本质:中间的短板没有用! 复杂度 O(n) */ import java.util.Stack; /* 用堆栈计算每一块板能延伸到的左右边界 对每一块板 堆栈顶矮,这一块左边界确定,入栈 堆栈顶高,堆栈顶右边界确定,出栈,计算面积 入栈时左边界确定 出栈时右边界确定 堆栈里元素是递增的 本质:中间的短板没有用! 复杂度 O(n) */ public class Solution { public int largestRectangleArea(int[] height) { Stack<Integer> s = new Stack<>(); int len = height.length; int maxArea = 0; //i 可超出len边界 for (int i = 0; i <= len; i++) { // 直方图的边界处理, 如果刚好超边界, 则当前高度为0 int cur = (i == len ? 0 : height[i]); if (s.empty() || cur >= height[s.peek()]) { s.push(i); } else { int p = s.pop(); // 左边界, 如果stack已空则左边界为0, 否则为stack.peek()+1 int left = (s.empty() ? 0 : s.peek() + 1); maxArea = Math.max(maxArea, height[p] * (i - left)); i--; } } return maxArea; } }
//以height的每个数作为基准来构建长方形,即从第i个值往前查找连续N个大于等于height[i]的值, //往后查找M个大于等于height[i]的值,即可以构建一个(M+N+1) * height[i]的长方形 //取其中面积最大的一个 public class Solution { public int largestRectangleArea(int[] height) { int max = 0; for(int i = 0; i < height.length; i++){ int len = 1; for(int j = i - 1; j >= 0; j--){ if(height[j] >= height[i]){ len++; }else { break; } } for(int k = i + 1; k < height.length; k++){ if(height[k] >= height[i]){ len++; }else { break; } } max = Math.max(max,len * height[i]); } return max; } }
For explanation, please see http://www.geeksforgeeks.org/largest-rectangle-under-histogram/
public class Solution { public int largestRectangleArea(int[] height) { int len = height.length; Stack<Integer> s = new Stack<Integer>(); int maxArea = 0; for(int i = 0; i <= len; i++){ int h = (i == len ? 0 : height[i]); if(s.isEmpty() || h >= height[s.peek()]){ s.push(i); }else{ int tp = s.pop(); maxArea = Math.max(maxArea, height[tp] * (s.isEmpty() ? i : i - 1 - s.peek())); i--; } } return maxArea; } }