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

牛舍的占地面积

https://www.nowcoder.com/practice/4d9d9bf23d874688aee6fc1ac5bf6902

考察的知识点:栈的基本操作;

解答方法分析:

  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;
    }
};

全部评论

相关推荐

点赞 评论 收藏
分享
码农索隆:想看offer细节
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务