首页 > 试题广场 >

最大矩形面积

[编程题]最大矩形面积
  • 热度指数: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

输出

10
package com.yf.meituan;

import java.util.Scanner;

/*
 * 遍历数组每一个值,然后用两个指针从当前位置向两边寻找左右边界,大于等于当前值时则对应指针加1,
 * 这样最后得到以当前值为最小高度的矩形宽度,然后计算面积并与最大值比较并保存其中最大的值
 */
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] height = new int[n];
		for(int i =0;i<n;i++){
			height[i] = sc.nextInt();
		}

		int maxArea = -1;
		for(int i = 0;i<n;i++){
			int left=i;
			int right=i;

          //计算以当前值为最小高度的矩形面积
			while(left > 0 && height[left-1] >= height[i])  left--;//寻找左边界
			while(right < n-1 && height[right+1] >= height[i])  right++;//寻找右边界
			int tempArea = (right-left+1) * height[i];
			
			if(maxArea<tempArea) maxArea=tempArea;
		}

		System.out.println(maxArea);
	}
}

编辑于 2017-09-01 17:26:16 回复(5)
import java.util.Scanner; 
import java.util.Arrays; 
public class Main { 
    public static int getMaxArea(int[] height) { 
        int len = height.length;
        int max = 0;//存储最大面积的
        for(int i = 0;i<len;i++){//i表示依次遍历每一个高度
            int minHeight = height[i];//设i为最小高度  
            for(int j=(i+1); j<len; j++){  
                minHeight = Math.min(minHeight, height[j]);//找出i之后的最小高度
                max = Math.max(max, (j-i+1)*minHeight);//计算以最小高度为高度的最大面积值
            }  
       }
        return max;
    }
    public static void main(String args[]) { 
        Scanner sc = new Scanner(System.in); 
        int n = sc.nextInt();
        int [] arr = new int[n];
        for(int i=0;i<n;i++){ 
          arr[i]=sc.nextInt();
        } 
       System.out.println(getMaxArea(arr));
    } 
}

发表于 2017-07-14 17:08:59 回复(14)
//网上找到的,线性时间复杂度
//巧妙地用了两个stack,一个stack保存高度,另一个保存index遍历height数组,
//1 如果stack为空或者当前元素的高度大于height stack顶元素(前一个元素)的高
//  度 => 把当前高度额index分别添加到两个stack顶
//2 如果当前元素的高度等于height stack顶元素的高度 => 什么都不做
//3 如果当前元素的高度小于height stack顶元素的高度 => 持续弹栈直到当前元素的高度
//  大于栈顶元素,并每次都计算面积(height * (current index - popped index)),
//  保存最大面积。最后把当前高度和最后一个弹出的index(非当前index) 重新压入栈中
//4 处理完height数组,如果stack非空,则一一弹栈并计算面积。
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int main()
{
  int n;
  while(cin>>n)
    {
      vector<int> h(n,0);
      for(int i=0;i<n;++i)
        cin>>h[i];

      stack<int> h_stack;
      stack<int> index_stack;

      h_stack.push(h[0]);
      index_stack.push(0);

      long long area=h[0];

      for(int i=1;i<n;++i)
        {
          if(h[i]>h_stack.top())
            {
              h_stack.push(h[i]);
              index_stack.push(i);
            }
          else if(h[i]==h_stack.top())
            ;
          else /*h[i]<h_stack.top()*/
            {
              int tmp_index;
              while(!h_stack.empty() && h[i]<h_stack.top())
                {
                  tmp_index=index_stack.top();
                  area=max(area,(long long)(h_stack.top()*(i-tmp_index)));
                  h_stack.pop();
                  index_stack.pop();
                }
                  h_stack.push(h[i]);
                  index_stack.push(tmp_index);
            }
        }

      while(!h_stack.empty())
        {
          area=max(area,(long long)(h_stack.top()*(n-index_stack.top())));
          h_stack.pop();
          index_stack.pop();
        }
      cout<<area<<endl;
    }
}

/*
//暴力法
#include <iostream>
#include <vector>
using namespace std;

int main()
{
  int n;
  while(cin>>n)
    {
      vector<int> h(n,0);
      for(int i=0;i<n;++i)
        cin>>h[i];
      int minH=0;//之前的最小高度
      long long area=0;//总的面积
      for(int i=0;i<n;++i)
        {
          minH=h[i];
          for(int j=i;j<n;++j)
            {
              minH=min(minH,h[j]);
              area=max(area,(long long)(minH*(j-i+1)));
            }
        }
      cout<<area<<endl;
    }
  return 0;
}
*/


编辑于 2017-06-24 16:47:28 回复(0)

// 对每个数判断连续最大面积,(这和求连续最大子序列相似),总共进行N趟
// 时间复杂度为o(N^2)

#include<iostream>
#include<algorithm>
using namespace std;

int main(){
    int n,a[10001];
    double smax,simax,si;
    while(cin>>n){
        for(int i=0;i<n;i++)cin>>a[i];
        for(int i=0;i<n;i++){
            int h=a[i];
            simax=0;si=0;
            for(int j=0;j<n;j++){
                if(a[j]>=h)si+=h;
                else si=0;
                if(si>simax)simax=si;
            }
            if(simax>smax)smax=simax;
        }
        cout<<(int)smax<<endl;
    }
    return 0;
}
编辑于 2017-08-24 13:21:50 回复(1)
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String strN;
        while((strN = br.readLine()) != null){
            int n = Integer.parseInt(strN);
            int[] heights = new int[n];
            String[] strArr = br.readLine().trim().split(" ");
            for(int i = 0; i < n; i++) heights[i] = Integer.parseInt(strArr[i]);
            System.out.println(solve(heights));
        }
    }
    
    // 依次选择每一根柱子向两边扩展,求出每一根柱子扩展出去的最大矩形
    private static int solve(int[] heights) {
        int max = 0;
        for(int i = 0; i < heights.length; i++) {
            int temp = heights[i];
            //向左扩展
            for(int left = i - 1; left >=0; left--) {
                if(heights[left] < heights[i]) {
                    break;
                }else {
                    temp += heights[i];
                }
            }
            //向右扩展
            for(int right = i + 1; right < heights.length; right++) {
                if(heights[right] < heights[i]) {
                    break;
                }else {
                    temp += heights[i];
                }
            }
            if(temp > max) {
                max = temp;
            }
        }
        return max;
    }
}

发表于 2020-10-16 16:03:54 回复(0)
//栈维护一个递增序列
#include<stack>
#include<vector>
#include<iostream>
using namespace std;
int main()
{
    int n,res=0;cin>>n;
    stack<int> st;
    vector<int> vin;
    for(int i=0;i<n;i++)
    {    int tmp; cin>>tmp;
         vin.push_back(tmp);
         while(st.size() != 0 && vin[st.top()] >tmp )
         {    
               int ind = st.top(),ind_2; 
               st.pop();
               if(st.size() ==0 )
                    ind_2 =-1;
                else
                    ind_2 = st.top();
             //ind为前一个递增序列的最后高度,ind2表示ind2到ind区间内高度都大于等于st[ind]
               res = max(res,vin[ind]*(i-ind_2-1) );
         }
         st.push(i);
    }
    while(st.size() != 0) //栈还未清空的情况,表示最后一个区间比之前的大,仍然递增
    {
        int ind = st.pop(),ind_2;
        st.pop();
        if(st.size() ==0 )
            ind_2 =-1;
        else
            ind_2 = st.top();
        res = max(res,(n - ind_2 - 1)*vin[ind] )  ;
    }
    cout<<res<<endl;
}

//分治法

#include<vector>
#include<iostream>
using namespace std;
int func(vector<int> &num,int st,int ed)
{
   if(st>ed)   //min_ind 等于st  会出现 mid - 1 < st的情况
        return 0;
    if(st == ed)
        return num[st];
    
    //寻找区间范围内最矮的高度,并获取对应的索引
    int min_num,min_ind=-1;
    for(int i=st;i<=ed;i++)
    {
        if(min_ind == -1 || num[i]< min_num)
        {
            min_ind = i;
            min_num = num[i];
        }
    }
    
    /*确定了最矮柱子以后,矩形的宽尽可能往两边延伸。
      在最矮柱子左边的最大面积矩形(子问题)。
      在最矮柱子右边的最大面积矩形(子问题)*/
    
    int one = min_num * (ed-st+1);
    //将左右区间的最大面积求出,递归区间二分法
    int rl = max(func(num,st,min_ind-1),func(num,min_ind+1,ed));
    return max(one,rl);
}
int main()
{
    int n,tmp;cin>>n;
    vector<int> num;
    while(n--)
    {
        cin>>tmp;
        num.push_back(tmp);
    }
    int res = func(num,0,num.size()-1);
    cout<<res<<endl;
    return 0;
}

编辑于 2019-09-02 15:29:05 回复(0)
借鉴前面的分治法:
var n = readline();
    var line = readline().split(' ');
    function largestarea(line){
        var len = line.length;
        var index = line.indexOf(Math.min.apply(null,line).toString());
        var value1 = line[index] * len;
        if(index!=0){
            var value2 = largestarea(line.slice(0, index));
        }else{
            var value2 = 0;
        }
        if(index!= len-1){
            var value3 = largestarea(line.slice(index+1));
        }else{
            var value3=0;
        }
        return Math.max(value1,value2,value3);
    }
    print(largestarea(line))


发表于 2018-10-08 18:42:15 回复(0)

复杂度O(n)
单调栈 or dp
可以参考hdu 1506
大致思路:把每一个点当成高,然后获取他的最左端,最右端
import java.math.BigInteger;
import java.util.Scanner;

public class Main {

    final static int maxn = 10000 + 10;
    public static void main(String []args){

        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            int n = in.nextInt();
            int[] a = new int[maxn];
            int[] L = new int[maxn];
            int[] R = new int[maxn];
            for(int i = 1;i <= n;i ++){
                a[i] = in.nextInt();
            }

            for(int i = 1;i <= n;i ++){
                L[i] = R[i] = i;
            }
            L[0] = R[n + 1] = -1;
            for(int i = 1;i <= n;i ++){
                while(a[L[i] - 1] >= a[i]){
                    L[i] = L[L[i] - 1];
                }
            }

            for(int i = n;i >= 1;i --){
                while(a[R[i] + 1] >= a[i]){
                    R[i] = R[R[i] + 1];
                }
            }

            long ans = 0;
            for(int i = 1;i <= n;i ++){
                ans = Math.max(ans,(long)(R[i] - L[i] + 1) * a[i]);
            }
            System.out.println(ans);
        }
        in.close();
    }
}
编辑于 2018-07-14 17:46:03 回复(0)
#include<iostream>
#include<vector>
using namespace std;
int main()
    {
    int n;
    while(cin>>n)
        {
        vector<int> vec(n,0);
        for(auto &it:vec)
            cin>>it;
        int max=0;
        for(int i=0;i<n;i++)
            {
            int temp=1;
            for(int j=i-1;j>=0;j--)
                if(vec[j]>=vec[i])
                    temp++;
                else
                    break;
            for(int j=i+1;j<n;j++)
                if(vec[j]>=vec[i])
                    temp++;
                else
                    break;
            temp = temp*vec[i];
            max<temp?max=temp:max=max;
        }
        cout<<max<<endl;
    }
return 0;
}
暴力解法
发表于 2017-08-31 13:43:56 回复(0)
'''
分治法:最大矩形面积只可能有三种情况:
1. 取决于高度最小的柱子,此时面积等于高度乘总长度;
2. 最大面积出现在高度最小的柱子左边;
3. 最大面积出现在高度最小的柱子右边;
'''
n = int(raw_input())
h = [int(x) for x in raw_input().split()]

def largestarea(a):
    l = len(a)
    idx = a.index(min(a))

    value1 = a[idx] * l

    if idx != 0:
        value2 = largestarea(a[0:idx])
    else:
        value2 = 0
    if idx != l-1:
        value3 = largestarea(a[idx+1:l])
    else:
        value3 = 0
    return max(value1, value2, value3)

print largestarea(h)

发表于 2017-06-29 14:41:44 回复(12)
#以每个柱为基准向左向右递归扩张找每个柱能扩张的最大宽度
class Solution:
    #向左扩张
    def width_left(self, index, height, h):
        #地址小于0 或者 高度小于自身
        if index < 0 or height > h[index]:
            return 0
        else: #地址大于等于0 高度大于等于自身    
            return self.width_left(index-1, height, h) + 1

    #向右扩张
    def width_right(self, index, height, h):
        #地址大于最大地址 或者 高度小于自身
        if index > len(h)-1 or height > h[index]:
            return 0
        else: #地址小于等于最大地址 高度大于等于自身
            return 1 + self.width_right(index+1, height, h)

    

n = int(input())
h = [int(x) for x in input().split(" ")]
print()

Area = []

#遍历所有的柱
for i in range(n):   
    s1 = Solution()
    width = s1.width_left(i, h[i], h)+s1.width_right(i, h[i], h)-1 #最大宽, 减掉多加的一个1
    Area.append(int(h[i] * width))    
    print(h[i]*"■ ",h[i],"\t\t", "扩张最大宽度 =",width)

print()    
print("最大面积=", max(Area))

-----------------------------------------------------------------
输入:
6
1 2 3 4 5 6

输出:
■ ■ ■ ■ ■ ■  6          扩张最大宽度 = 1
■  1                  扩张最大宽度 = 7
■ ■ ■  3              扩张最大宽度 = 2
■ ■ ■ ■  4              扩张最大宽度 = 1
■  1                  扩张最大宽度 = 7
■ ■  2                  扩张最大宽度 = 2
■ ■ ■ ■ ■  5          扩张最大宽度 = 1

最大面积 = 7
编辑于 2020-09-13 14:06:23 回复(0)
//
// Created by jt on 2020/9/2.
//
#include <vector>
#include <iostream>
#include <stack>
using namespace std;

int monotoneStack(vector<int> &vec);

int main() {
    int n;
    cin >> n;
    vector<int> vec;
    for (int i = 0; i < n; ++i) { int a; cin >> a; vec.push_back(a); }
    cout << monotoneStack(vec) << endl;
}


int monotoneStack(vector<int> &vec) {
    vec.push_back(0);
    int maxVal = 0;
    stack<int> st;
    for (int i = 0; i < vec.size(); ++i) {
        while(!st.empty() && vec[i] < vec[st.top()]) {
            int height = vec[st.top()];
            st.pop();
            int left = st.empty() ? -1 : st.top();
            int width = i - (left+1);
            maxVal = max(maxVal, height * width);
        }
        st.push(i);
    }
    return maxVal;
}
发表于 2020-09-02 19:43:37 回复(0)
//非常好懂的一个递归 依次求局部最大
#include<iostream>
#include<vector>
#include<limits.h>
using namespace std;

class Solution{
  public:
    int getMaxArea(vector<int> arr,int low,int high){
        if(low > high){
            return 0;
        }
        if(low == high){
            return arr[low];
        }
        int k =low;
        int min = INT_MAX;
        for(int i=low;i<=high;i++){
            if(arr[i] < min){
                min = arr[i];
                k = i;
            }
        }
        int maxArea = min*(high-low+1);
        maxArea = max(maxArea,max(getMaxArea(arr,low,k-1),getMaxArea(arr,k+1,high)));
        return maxArea;

    }
};

int main(){
    int n;
    cin>>n;
    vector<int> arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    Solution c1;
    cout<<c1.getMaxArea(arr,0,n-1);
    return 0;
}

发表于 2020-05-29 18:16:20 回复(0)

美团2017 JAVA

[编程题]大富翁游戏
[编程题]拼凑钱币
[编程题]最大矩形面积
[编程题]最长公共连续子串

矩形的高度取决于最短的柱子,我的解法是通过排个序,从短柱子开始求矩形面积。这个排序对性能的影响还没想明白。另外stream特性是真的好用,一旦拥有,爱不释手。

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    int max=0;
    public static void main(String[] args){
        Main s=new Main();
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        int h[]=new int[n];
        for (int i=0;i<n;i++){
            h[i]=in.nextInt();
        }
        Arrays.stream(h).distinct().forEach(x->s.s(x,h));
        System.out.print(s.max);
    }
    //当前矩形面积如果大于max就更新max
    void s(int a,int[] h){
        int cnt=0;
        for(int i:h){
            if (i>=a){
                cnt+=a;
                if (cnt>max){
                    max=cnt;
                }
            }else{
                cnt=0;
            }
        }
    }
}
编辑于 2020-04-19 17:46:09 回复(0)
#include<stdio.h>

int main(void){
    int n;
    scanf("%d",&n);
    int arr[n];
    int max_area=0; //最大面积 
    int i,j;
    for(i=0;i<n;i++){//输入边长 
        scanf("%d",&arr[i]);
    }
    
    //定义栈(动态规划)
    int stack[n];
    int top=-1;//-1代表栈空
    int temp; //保存边长 
    int area; //保存面积 
    for(i=0;i<n;i++){
        
        if(top==-1 || arr[stack[top]]<=arr[i]){ //栈为空或者Hi<Hi+1 
            stack[++top]=i; 
        }else{//若不递增 
            temp=stack[top--];//取出最大边长下标 
            area=arr[temp]*(top==-1?i:i-stack[top]-1);//计算面积 
            //printf("%d\t%d\t%d\n",temp,top,area);
            if(area>max_area){
                max_area=area; 
            }
            i--;
        
    }
    while(top!=-1){
        temp=stack[top--];//取出最大边长下标 
        area=arr[temp]*(top==-1?i:i-stack[top]-1);//计算面积 
        //printf("%d\t%d\t%d\n",temp,top,area);
        if(area>max_area){
            max_area=area; 
        }
    }
    /* 暴力解法 
    for(i=0;i<n;i++){
        int low=arr[i];//标记最短的边长 
        int temp=0;//保存矩形面积 
        for(j=i;j<n;j++){ //计算i与j之间最大的面积 
            //先计算出i与j之间最短的边长 
            if(low>arr[j]){ 
                low=arr[j];
            }
            //计算矩形面积
            temp=(j-i+1)*low;
            //保存最大面积 
            if(temp>max_area){
                max_area=temp;
            
        }  
    }*/
    printf("%d",max_area);
    return 0;
}
发表于 2020-04-05 15:22:18 回复(0)
hid头像 hid
def findera(li):
    minli=min(li)
    a.append(len(li)*minli)
    left = li[:li.index(minli)]
    right = li[li.index(minli)+1:]
    if len(left)>=1:
        findera(left)
    if len(right)>=1:
        findera(right)
    return a
a=[]
li = []
n = int(input())
li=[int(i) for i in input().split()]
print(max(findera(li)))


发表于 2019-10-18 16:00:32 回复(0)
维护栈的解法,时间复杂度O(n),空间复杂度O(n),每次出栈时维护包括出栈序列在内的面积最大值,最后剩下递增序列,包括索引在内的最大面积在索引与末尾之间。
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = newBufferedReader(newInputStreamReader(System.in));
        while(in.ready()) {
            intcount = Integer.parseInt(in.readLine());
            String[] strings = in.readLine().split(" ");
            int[] nums = newint[count];
            for(inti = 0; i < count; i++) {
                nums[i] = Integer.parseInt(strings[i]);
            }
            /* got nums */
            Stack<Integer> stack = newStack<>();
            stack.push(-1);
            intmaxArea = 0;
            for(inti = 0; i < nums.length; i++) {
                while(stack.peek() != -1&& nums[i] <= nums[stack.peek()]) {//当呈现下降趋势时
                    maxArea = Math.max(maxArea, nums[stack.pop()] * (i - stack.peek() - 1));
                }
                stack.push(i);
            }
            while(stack.peek() != -1) {
                maxArea = Math.max(maxArea, nums[stack.pop()] * (nums.length - stack.peek() - 1));
            }
            System.out.println(maxArea);
        }
        in.close();
    }
}

发表于 2019-06-15 09:11:02 回复(0)
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)
n =int(input())
arr =[int(x) forx ininput().split()]
  
defsolution(arr):
    l =len(arr)
    area =min(arr)*l
    idx =arr.index(min(arr))
    ifidx !=0:
        area =max(solution(arr[:idx]), area)
    ifidx !=l-1:
        area =max(solution(arr[idx+1:]), area)
    returnarea
         
print(solution(arr))
发表于 2019-04-23 14:54:42 回复(0)
 
a=int(input())
c=input()
b=list(map(int,c.split())) def get_s(a,b):
    end_s=[]
    j=0    while j<a :  for i in range(a-j):
                temp_b=b[0+j:j+i+1]
                s=sorted(temp_b)[0]*(i+1)
                end_s.append(s)
                end_s.sort(reverse=True)
         j+=1 print(end_s[0])
get_s(a,b)
#暴力一波流,超不超时看脸。

编辑于 2018-11-04 21:12:25 回复(0)