算法：柱状图中最大矩形

 题目要求

给定 n 个非负整数，用来表示柱状图中各个柱子的高度，并且每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。

• 以下是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。
  
• 图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。如下：

• 示例：

输入: [2,1,5,6,2,3]输出: 10 //柱状图中最大矩形//枚举宽，固定一边枚举另一边，然后计算面积 class Solution { public:int largestRectangleArea(vector<int>& heights) {int n = heights.size();int ans = 0;// 枚举左边界for (int left = 0; left < n; ++left) {int minHeight = INT_MAX;// 枚举右边界for (int right = left; right < n; ++right) {// 确定高度minHeight = min(minHeight, heights[right]);// 计算面积ans = max(ans, (right - left + 1) * minHeight);}}return ans;} };//枚举高 class Solution { public:int largestRectangleArea(vector<int>& heights) {int n = heights.size();int ans = 0;for (int mid = 0; mid < n; ++mid) {// 枚举高int height = heights[mid];int left = mid, right = mid;// 确定左边界，取左边界最高的那个while (left - 1 >= 0 && heights[left - 1] >= height) {--left;}// 确定右边界，取右边界最高的那个while (right + 1 < n && heights[right + 1] >= height) {++right;}// 计算面积ans = max(ans, (right - left + 1) * height);}return ans;} };//单调栈 func largestRectangleArea(heights []int) int {n := len(heights)left, right := make([]int, n), make([]int, n)//栈mono_stack := []int{}//取左边的第一个小于当前的for i := 0; i < n; i++ {//栈顶元素大于或等于当前元素就出栈for len(mono_stack) > 0 && heights[mono_stack[len(mono_stack)-1]] >= heights[i] {//出栈mono_stack = mono_stack[:len(mono_stack)-1]}if len(mono_stack) == 0 {left[i] = -1} else {left[i] = mono_stack[len(mono_stack)-1]}mono_stack = append(mono_stack, i)}//取右边的第一个小于当前的mono_stack = []int{}for i := n - 1; i >= 0; i-- {//栈顶元素大于或等于当前元素就出栈for len(mono_stack) > 0 && heights[mono_stack[len(mono_stack)-1]] >= heights[i] {//出栈mono_stack = mono_stack[:len(mono_stack)-1]}if len(mono_stack) == 0 {right[i] = n} else {right[i] = mono_stack[len(mono_stack)-1]}mono_stack = append(mono_stack, i)}ans := 0for i := 0; i < n; i++ {ans = max(ans, (right[i] - left[i] - 1) * heights[i])}return ans }func max(x, y int) int {if x > y {return x}return y }

 

总结

以上是生活随笔为你收集整理的算法：柱状图中最大矩形的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。