最大矩形面积

[编程题]最大矩形面积

热度指数：7102 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一组非负整数组成的数组h，代表一组柱状图的高度，其中每个柱子的宽度都为1。在这组柱状图中找到能组成的最大矩形的面积（如图所示）。入参h为一个整型数组，代表每个柱子的高度，返回面积的值。

输入描述:

输入包括两行,第一行包含一个整数n(1 ≤ n ≤ 10000)
第二行包括n个整数,表示h数组中的每个值,h_i(1 ≤ h_i ≤ 1,000,000)

输出描述:

输出一个整数,表示最大的矩阵面积。

示例1

输入

6
2 1 5 6 2 3

输出

算法知识视频讲解

Java

offer快到碗里来啊！

import java.util.Scanner;
/**
 * @Classname ZuiDaJuxingMianJi
 * @Description TODO
 * @Date 19-6-1 下午4:05
 * @Created by mao<tianmao818@qq.com>
 */
public class Main {
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while (sc.hasNext()){
            int n=sc.nextInt();
            int[] heights=new int[n];
            for(int i=0;i<n;i++){
                heights[i]=sc.nextInt();
            }

            int ans=0;
            for(int i=0;i<n;i++){
                //if(i+1<n && heights[i]<heights[i+1]){
                  //  continue;
                //}
                int minH=heights[i];
                for(int j=i;j>=0;j--){
                    minH=Math.min(minH,heights[j]);
                    ans=Math.max(ans,minH*(i-j+1));
                }
            }
            System.out.println(ans);
        }
    }
}

发表于 2019-06-01 16:39:35 回复(0)

Java

拂晓201808101620698

import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        /**
         * 利用递增栈处理，如果遇到比栈顶元素小或者相等的数就开始处理计算面积，栈中存储的为坐标
         */
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        long[] heights=new long[n+1];
        for(int i=0;i<n;i++) {
            heights[i]=sc.nextLong();
        }
heights[n]=0;
        Stack<Integer> stack=new Stack<>();
        long area=0;
        for(int i=0;i<n+1;i++) {
            //如果栈为空或者当前元素大于栈顶元素则把当前元素存进栈中
            if(stack.empty()||heights[i]>heights[stack.peek()]) {
                stack.push(i);
            }else {
                //否则就开始计算面积
                int cur=stack.pop();
                area=Math.max(area, heights[cur]*(stack.empty()?i:(i-stack.peek()-1)));
                i--;//让i返回当前值
            }
        }
        System.out.println(area);


    }
}

编辑于 2018-09-06 20:07:08 回复(0)