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

知识点：单调栈

思路：单调栈的应用，先求出左右牛舍的最小长度然后遍历牛舌求出最大占地面积

编程语言：java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param areas int整型一维数组
     * @return int整型
     */
    public static int maxArea(int[] areas) {
        // 预处理两边最近的比其大的位置
        int n = areas.length;
        int[] l = new int[n];
        int[] r = new int[n];

        Stack<Integer> stk = new Stack<>();
        for (int i = 0; i < n; i++) {
            while (!stk.isEmpty() && areas[stk.peek()] >= areas[i])
                stk.pop();
            l[i] = stk.isEmpty()? -1 : stk.peek();
            stk.push(i);
        }

        stk = new Stack<>();
        for (int i = n - 1; i >= 0; i--) {
            while (!stk.isEmpty() && areas[stk.peek()] >= areas[i])
                stk.pop();
            r[i] = stk.isEmpty()? n : stk.peek();
            stk.push(i);
        }

        int res = 0;
        for (int i = 0; i < n; i++) {
            res = Math.max(res, (r[i] - l[i] - 1) * areas[i]);
        }
        return res;
    }

}