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

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;
    }
}

本题知识点分析：

单调栈

本题解题思路分析：

分析题意我们知道，决定面积的是区间内最小的点，所以我们只需要考虑每一个点作为最小的点时，所处区间的面积。对于每一个点，需要维护左右两端比自己小的点，左边界为0，右边界为n.

我们可以使用单调栈来维护areas[i]的左右边界，思路类似于动态规划的单调栈优化单调上升子序列。我们首先用两次遍历，预处理每个端点的左右边界，然后再遍历每个端点，用自己的长度以及到左右两侧的距离之和相乘得到面积，维护最大的ans。

本题使用编程语言: Java