题解 | #牛舍的占地面积#
牛舍的占地面积
https://www.nowcoder.com/practice/4d9d9bf23d874688aee6fc1ac5bf6902
考察的知识点:栈的基本操作;
解答方法分析:
- 创建一个空栈和两个辅助数组,分别用于记录每个柱子的左边界和右边界。
- 遍历柱子数组,对于每个柱子进行如下操作:如果栈为空,将当前柱子的下标入栈。如果栈不为空,判断当前柱子与栈顶柱子的高度关系:如果当前柱子的高度小于等于栈顶柱子的高度,将栈顶柱子的右边界设置为当前柱子的下标,并将栈顶柱子出栈。重复这个操作直到栈为空或者当前柱子的高度大于栈顶柱子的高度。如果栈不为空,将当前柱子的下标入栈。同时,将当前柱子的左边界设置为栈顶柱子的下标。
- 遍历柱子数组,对于每个柱子计算以该柱子作为高度的矩形的面积,并更新记录的最大面积。
- 返回最大面积。
所用编程语言: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; } };