题解 | #牛舍的占地面积#

知识点

动态规划

解题思路

题目的意思是在areas[a] 到areas[b]之间找到一组数面积最大，长相当于就是b - a + 1，宽就是areas[a]到areas[b]之间的最小值，长我们可以直接确定，难点就是找到其中的宽，并找到其中面积最大的。

定义一个数组minArr[][]，minArr[i][j]表示在areas[i]到areas[j]之间的最小值，当i=j时minArr[i][j]=areas[i],当i!=j时，minArr[i][j]=minArr[i][j-1]。因此根据这个数组就能找到最大面积。

Java题解

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param areas int整型一维数组 
     * @return int整型
     */
    public int maxArea (int[] areas) {
        // write code here
        int n = areas.length;
        int[][] minArr = new int[n][n]; //保存最小值
        int ans = 0;
        for (int i = 0; i < n; i++){
            minArr[i][i] = areas[i];
            ans = Math.max(ans,areas[i]);
            for (int j = i + 1; j < n; j++){
                minArr[i][j] = Math.min(minArr[i][j - 1],areas[j]);
                ans = Math.max(ans,minArr[i][j] * (j - i + 1));
            }
        }
        return ans;
    }
}