首页 > 试题广场 >

计算柱状图中最大的长方形面积。 如图所示，设一个柱状图中每个

[问答题]

计算柱状图中最大的长方形面积。

如图所示，设一个柱状图中每个柱子的密度均为 1 ，有一组非负整数 Height={1,3,6,7,2,6} 代表各个柱子的高，找出这个柱状图中最大的长方形的面积 Area=12 ，如右图阴影部分所示，图输入 Height={1,3 ， 6,7,2 ， 6} 返回 Area=12. （先简述思路，再写代码，语言不限）


添加回答
木槿心头像 木槿心
/**
 *把柱子x当成组成矩形的最小柱子，如果我们把每个柱子对应的矩形面积计算出来，求出其中最大的矩**形，就解决了这个问题。
 *我们要确定矩形的左右边界，左边界是柱子x左侧第一个小于x的柱子，右边界是x右侧小于x的柱子。
 *首先创建一个空栈。
 *如果栈为空，或者柱子大于栈顶的柱子，把柱子i压入栈中。
 *如果当前的柱子比栈顶柱子小，则出栈，并计算柱子对应的矩形面积。继续出栈，直到当前的柱子比
  *栈顶柱子大。
 *如果栈不为空，则依次弹出栈，计算矩形面积。
 *
 */

public int largestRectangleArea(int[] height) {
       int len = height.length;
       Stack<Integer> s = new Stack<Integer>();
       int tp;
       int areaWithTop;
       int maxArea = 0;
       int i = 0;
       while(i<len){
           int h = (i == len ? 0 : height[i]);
           if(s.isEmpty() || h >= height[s.peek()]){
               s.push(i);
               i++;
           }else{
               tp = s.pop();
               areaWithTop = height[tp] * (s.empty() ? i:i-1-s.peek() );
               if(maxArea < areaWithTop) {
               maxArea =areaWithTop;
               }
           }
       }
       
       while(!s.isEmpty()){
       tp = s.pop();
       areaWithTop = height[tp] * (s.empty() ? i:i-1-s.peek() );
       if(maxArea < areaWithTop) {
                maxArea =areaWithTop;
                }
       }
       return maxArea;
   } 
本题是leetcode上的题目，参考解答链接http://www.geeksforgeeks.org/largest-rectangle-under-histogram/

发表于 2017-02-28 19:32:02 回复(0)
提交观点

问题信息

编程基础
上传者：牛100
难度：
1条回答 2303浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号