题解 | #牛舍的占地面积# 单调栈解法

知识点

单调栈

题意和思路

这题题面太抽象了，不能加个图吗？？

样例一是这样的：

蓝色是这几个牛棚，橙色是那个盖布。

因为盖布的长度和最短的牛棚一致，我们考虑每个位置作为“最小”时对答案的贡献，然后我们可以发现，当某个位置作为最小值是，盖布的另一条边的长度等于左右两侧第一个比当前长度短的距离。求左右两侧第一个比当前值小的位置，是单调栈的基本用法。

之后遍历每个位置，计算它作为最短的边的贡献来统计答案即可。

时间复杂度

求左右最近的比当前小的位置的时间复杂度为

总体时间复杂度为

AC code（c++）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param areas int整型vector 
     * @return int整型
     */
    int maxArea(vector<int>& areas) {
        // 预处理两边最近的比其大的位置
        int n = areas.size();
        vector<int> l(n), r(n);
        stack<int> stk;
        for (int i = 0; i < n; i ++) {
            while (stk.size() and areas[stk.top()] >= areas[i]) stk.pop();
            if (stk.empty()) l[i] = -1;
            else l[i] = stk.top();
            stk.push(i);
        }

        stk = stack<int>();
        for (int i = n - 1; i >= 0; i --) {
            while (stk.size() and areas[stk.top()] >= areas[i]) stk.pop();
            if (stk.empty()) r[i] = n;
            else r[i] = stk.top();
            stk.push(i);
        }

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