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

知识点

单调栈

思路

假设n=areas.size()

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

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

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param areas int整型vector 
     * @return int整型
     */
    int maxArea(vector<int>& areas) {
        // write code here
        int n=areas.size();
        stack <int>st;
        vector<int>l(n),r(n);//左右边界

        for(int i=0;i<n;i++)//右边界
        {
            while(!st.empty()&&areas[st.top()]>=areas[i])st.pop();
            if(st.empty())l[i]=-1;//下界为0-1
            else l[i]=st.top();
            st.push(i);
        }
        
        for(int i=n-1;i>=0;i--)//左边界
        {
            while(!st.empty()&&areas[st.top()]>=areas[i])st.pop();
            if(st.empty())r[i]=n;//上界为n
            else r[i]=st.top();
            st.push(i);
        }
        
        int ans=-1;
        for(int i=0;i<n;i++)
        {
            ans=max(ans,areas[i]*(r[i]-l[i]-1));//更新面积
        }
        return ans;
    }
};