本文主要是介绍Day52- 单调栈part03,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
一、柱状图中最大的矩形
题目一:84. 柱状图中最大的矩形
84. 柱状图中最大的矩形
给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。
求在该柱状图中,能够勾勒出来的矩形的最大面积
栈中保存的是每个柱子的索引,栈中索引对应的柱子高度是递增的,所以每个柱子的右边界就是其右侧第一个高度不足的位置。同理,柱子的左边界是其左侧第一个高度不足的位置。
class Solution {
public:int largestRectangleArea(vector<int>& heights) {int n = heights.size();vector<int> left(n), right(n, n);stack<int> mono_stack;for (int i = 0; i < n; ++i) {while (!mono_stack.empty() && heights[mono_stack.top()] >= heights[i]) {right[mono_stack.top()] = i;mono_stack.pop();}left[i] = (mono_stack.empty() ? -1 : mono_stack.top());mono_stack.push(i);}int ans = 0;for (int i = 0; i < n; ++i) {ans = max(ans, (right[i] - left[i] - 1) * heights[i]);}return ans;}
};
这篇关于Day52- 单调栈part03的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!