直方图中的最大矩形

//类似于中心拓展法，针对每个位置，找到前后大于等于该高度元素的数量
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;
    }
}