We read every piece of feedback, and take your input very seriously.
To see all available qualifiers, see our documentation.
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Difficulty: 困难
Related Topics: 栈, 数组, 单调栈
给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。
求在该柱状图中,能够勾勒出来的矩形的最大面积。
示例 1:
输入:heights = [2,1,5,6,2,3] 输出:10 解释:最大的矩形为图中红色区域,面积为 10
示例 2:
输入: heights = [2,4] 输出: 4
提示:
Language: JavaScript
/** * @param {number[]} heights * @return {number} */ // 分治法 // 从高度值最小的高度的最大面积 (end-start+1) * height[min],将该面积与高度最小的柱子左边和右边形成的最大面积来比较。分治的最后是每一个矩形的面积。 const largestRectangleArea = (heights) => { let maxArea = 0 const stack = [] // 单调递增栈 注意栈存的是下标 heights = [0, ...heights, 0] // 在heights数组前后增加哨兵 用来清零单调递增栈里的元素 for (let i = 0; i < heights.length; i++) { // 当前元素对应的高度小于栈顶元素对应的高度时 while (heights[i] < heights[stack[stack.length - 1]]) { const stackTopIndex = stack.pop() // 出栈 maxArea = Math.max( // 计算面积 并更新最大面积 maxArea, heights[stackTopIndex] * (i - stack[stack.length - 1] - 1) // 高乘宽 ) } stack.push(i) // 当前下标加入栈 } return maxArea }
The text was updated successfully, but these errors were encountered:
No branches or pull requests
84. 柱状图中最大的矩形
Description
Difficulty: 困难
Related Topics: 栈, 数组, 单调栈
给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。
求在该柱状图中,能够勾勒出来的矩形的最大面积。
示例 1:
示例 2:
提示:
Solution
Language: JavaScript
The text was updated successfully, but these errors were encountered: