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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param areas int整型一维数组
     * @return int整型
     */
   public int maxArea (int[] areas) {
        // write code here
        Stack<Integer> stack = new Stack<>();
        int area = 0;
        for(int i=0;i<areas.length;i++){
            while(!stack.isEmpty() && areas[i]<=areas[stack.peek()]){
                int top = areas[stack.pop()];
                int right = i;
                int left = stack.isEmpty()?-1:stack.peek();
                area = Math.max(area,top*(right-left-1));
            }
            stack.add(i);
        }

        while(!stack.isEmpty()){
            int top = areas[stack.peek()];
            int right = stack.pop();
            int left = stack.isEmpty()?-1:stack.peek();
            area = Math.max(area,top*(right-left));
        }
        return area;
    }
}

本题考察的知识点是单调栈的应用，所用编程语言是java.

我们首先想一想如何用暴力算法求出此题，我们可以这样考虑依次用数组每个值当做牛舍的高度，然后往两边扩展看最长的长度是多少，然后算出面积，然后我们比较用数组每个值当做牛舍的高度求出的面积，以此得出最大值。

然后我们想想往两边扩展时求边界能不能优化一下，以此单调栈的作用就出来了。我们维持一个单调递增的栈，然后与数组中的值依次比较，如果栈为空或者当前数组元素值大于栈顶元素对应的数组元素值，直接将当前数组元素下标直接入栈。如果栈不为空且当前数组元素不大于栈顶元素对应的数组元素时，那么此时右边界显而易见的就是下标i,由于是单调递增的栈，左边界自然是单调栈中栈顶元素之后数组下标位置。

我们考虑一种极端情况，如果栈不为空且当前数组元素不大于栈顶元素对应的数组元素时，此时栈中只有一个元素，那么左边界如何确定，我的答案是设置为-1，然后此时长度为i