10个网站做站群,凡科商城和有赞哪个好,建设网站一定要电脑吗,react.js做的网站题目链接#xff1a;84. 柱状图中最大的矩形 - 力扣#xff08;LeetCode#xff09;
要找最大的矩形就是要找以每根柱子为高度往两边延申的边界#xff0c;要作为柱子的边界就必须高度不能低于该柱子#xff0c;否则矩形无法同高#xff0c;也就是需要找出以每根柱子为高…题目链接84. 柱状图中最大的矩形 - 力扣LeetCode
要找最大的矩形就是要找以每根柱子为高度往两边延申的边界要作为柱子的边界就必须高度不能低于该柱子否则矩形无法同高也就是需要找出以每根柱子为高、往两边找更低的柱子作为当前矩形的边界不含
可以用一个单调递增栈存储下标一直记录更高的柱子一旦碰到低的柱子此时栈顶可作为矩形的高当前柱子作为右边界不含栈顶往下一个元素可作为左边界不含计算完成后弹出栈顶这样可以以每个柱子的高度为矩形的高计算一次面积且边界都是尽可能延申的
class Solution {
public:int largestRectangleArea(vectorint heights) {int ans 0;heights.insert(heights.begin(), 0); // 尾哨兵heights.push_back(0); // 头哨兵stackint plus; // 单调递增栈for (int i 0; i heights.size(); i) {while (!plus.empty() heights[i] heights[plus.top()]) { // 找到更低的了说明找到边界int height heights[plus.top()];plus.pop();ans max(ans, height * (i - plus.top() - 1));}plus.push(i);}return ans;}
};
