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

当然可以，让我来总结一下。

题目考察的知识点

这道题目考察了数组的处理，贪心算法，以及单调栈的应用。

题目解答方法的文字分析

这道题目要求我们在一些不同大小的牛舍中选取连续的一部分来建造棚，以最大化能够覆盖的面积。有两种方法可以解决这个问题：暴力法和单调栈法。

暴力法

1. 初始化一个变量 maxArea 用于记录最大面积。
2. 遍历牛舍的长度，同时维护一个变量 minHeight 来记录当前最小的牛舍长度。
3. 从当前位置开始，向右扩展，计算以当前位置为起点，不断向右扩展得到的矩形面积，并更新 maxArea。
4. 返回最终的 maxArea。

单调栈法

1. 初始化一个变量 maxArea 用于记录最大面积，以及一个单调递增栈 st 来存储牛舍的索引。
2. 遍历牛舍的长度，如果当前牛舍的高度小于等于栈顶牛舍的高度，说明可以以栈顶牛舍为高度，根据栈内其他元素的顺序计算宽度，从而计算出一个可能的最大面积。然后不断弹出栈顶元素，直到栈为空或者当前牛舍高度大于栈顶牛舍高度。这种方式可以保证栈内的牛舍高度单调递增。
3. 返回最终的 maxArea。

本题解析所用的编程语言

本题解析所用的编程语言是 C++。

完整且正确的编程代码

暴力法

#include <vector>
using namespace std;

class Solution {
public:
    int maxArea(vector<int>& areas) {
        int maxArea = 0;  // 最大面积
        int n = areas.size();

        for (int i = 0; i < n; ++i) {
            int minHeight = areas[i];  // 当前最小牛舍长度

            // 以当前位置为起点，不断向右扩展，计算面积并更新最大面积
            for (int j = i; j < n; ++j) {
                minHeight = min(minHeight, areas[j]);
                maxArea = max(maxArea, minHeight * (j - i + 1));  // 长度是 j - i + 1
            }
        }

        return maxArea;
    }
};

单调栈

#include <vector>
#include <stack>
using namespace std;

class Solution {
public:
    int maxArea(vector<int>& areas) {
        int maxArea = 0;
        int n = areas.size();
        stack<int> st;  // 单调栈，存储牛舍的索引

        for (int i = 0; i <= n; ++i) {
            while (!st.empty() && (i == n || areas[i] <= areas[st.top()])) {
                int height = areas[st.top()];  // 当前牛舍的高度
                st.pop();

                int width = st.empty() ? i : i - st.top() - 1;
                maxArea = max(maxArea, height * width);
            }

            st.push(i);
        }

        return maxArea;
    }
};

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！