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

考察知识点：单调栈

题目分析：

为一个连续的牛舍盖棚时，牛舍的宽度是牛舍的个数，而牛舍的长度是其中的最小牛舍长。例如有三个牛舍，分别长 9 8 7 9 ，那么给这几个牛舍盖棚时，牛舍的宽度就是4，长度就是7。

连续牛舍中的最小长度影响了整个牛棚的长度。为了能得到更大的牛棚面积，我们发现，如果连续牛舍中有一个牛舍长度较小，那么最好是宽度能取宽一点，就是牛舍的个数多一点。先假设牛舍中最小的长度不变，我们扩大牛舍的范围，发现对结果是增益的，因为长不变，宽在增大；扩大的极限在哪里呢，就是取完所有牛舍，或者左边或右边再扩大一个牛舍时，最小长度会变小。

如果取这个更短的牛舍，结果可能得不偿失。但是我们也看看它的极限，也许是更好的解决方案呢？

因此，我们不断假设每一个牛舍都是连续牛舍中最短的牛舍，找到左右边界（即离该牛舍最近的更短的牛舍，或者是取完左边或右边所有牛舍），计算此时的面积。遍历所有牛舍时维护一个最小值即可。

我们发现，取离某个牛舍最近的更短的牛舍可以用单调栈来解决。

所用编程语言：C++

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param areas int整型vector 
     * @return int整型
     */
    int maxArea(vector<int>& areas) {
        // write code here
        int size = areas.size();
        stack<int> stk;
        vector<int> left(size), right(size);
        int res = 0;
	  //找到左边第一个比当前值小的牛舍长度
        for (int i = 0; i < size; i++) {
            while (!stk.empty() && areas[stk.top()] >= areas[i]) stk.pop();
            left[i] = stk.empty() ? -1 : stk.top();
            stk.push(i);
        }

        while (!stk.empty()) stk.pop();
        int l, r;
	  //找到右边第一个比当前值大的牛舍长度
        for (int i = size - 1; i >= 0; i--) {
            while (!stk.empty() && areas[stk.top()] >= areas[i]) stk.pop();
            right[i] = stk.empty() ? -1 : stk.top();
            stk.push(i);
            l = left[i] == -1 ? -1 : left[i];
            r = right[i] == -1 ? size : right[i];
            res = max(res, (r - l - 1) * areas[i]);
        }
        return res;

        
    }
};