题解 | #牛舍的占地面积#
牛舍的占地面积
https://www.nowcoder.com/practice/4d9d9bf23d874688aee6fc1ac5bf6902
- 题目考察的知识点 : 单调栈
- 题目解答方法的文字分析:
- 可以维护一个单调不降的栈 stk ,其中栈顶元素对应的牛舍高度最小、离当前位置最近的牛舍
- 从左往右遍历整个areas数组: 如果当前牛舍的高度大于等于栈顶元素的高度,则将栈顶元素出栈,并计算棚能覆盖到的最大面积;
- 重复步骤 1 直到栈为空或者当前牛舍的高度小于栈顶元素的高度;
- 将当前牛舍的下标入栈。
- 在上述过程中,如果栈不为空,则栈顶元素的下一个更短的牛舍到当前牛舍位置的距离为两者下标之差减去 1
- 本题解析所用的编程语言: Python
- 完整且正确的编程代码
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param areas int整型一维数组 # @return int整型 # class Solution: def maxArea(self , areas: List[int]) -> int: n = len(areas) stk = [-1] # 初始时,整个牧场的边界左侧无牛舍,因此将 -1 压入栈中 res = 0 for i in range(n): while stk[-1] != -1 and areas[i] <= areas[stk[-1]]: h = areas[stk.pop()] w = i - stk[-1] - 1 res = max(res, h * w) stk.append(i) while stk[-1] != -1: h = areas[stk.pop()] w = n - stk[-1] - 1 res = max(res, h * w) return res
牛客高频top202题解系列 文章被收录于专栏
记录刷牛客高频202题的解法思路