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

考察的知识点：栈的基本操作；

解答方法分析：

1. 创建一个空栈和两个辅助数组，分别用于记录每个柱子的左边界和右边界。
2. 遍历柱子数组，对于每个柱子进行如下操作：如果栈为空，将当前柱子的下标入栈。如果栈不为空，判断当前柱子与栈顶柱子的高度关系：如果当前柱子的高度小于等于栈顶柱子的高度，将栈顶柱子的右边界设置为当前柱子的下标，并将栈顶柱子出栈。重复这个操作直到栈为空或者当前柱子的高度大于栈顶柱子的高度。如果栈不为空，将当前柱子的下标入栈。同时，将当前柱子的左边界设置为栈顶柱子的下标。
3. 遍历柱子数组，对于每个柱子计算以该柱子作为高度的矩形的面积，并更新记录的最大面积。
4. 返回最大面积。

所用编程语言：C++；

完整编程代码：↓

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param areas int整型vector
     * @return int整型
     */
    int maxArea(vector<int>& areas) {
        int n = areas.size();
        stack<int> stk;
        vector<int> left(n, -1);
        vector<int> right(n, n);

        for (int i = 0; i < n; i++) {
            if (stk.empty()) {
                stk.push(i);
            } else {
                while (!stk.empty()) {
                    if (areas[i] <= areas[stk.top()]) {
                        right[stk.top()] = i;
                        stk.pop();
                    } else {
                        break;
                    }
                }
                if (!stk.empty()) {
                    left[i] = stk.top();
                }

                stk.push(i);
            }
        }

        int Area = 0;
        for (int i = 0; i < n; i++) {
            int area = areas[i] * (right[i] - left[i] - 1);
            Area = max(Area, area);
        }

        return Area;
    }
};