【LeetCode热题100】【栈】柱状图中最大的矩形

叶茂林

发布于 2024-04-08 08:24:34

690

发布于 2024-04-08 08:24:34

要找最大的矩形就是要找以每根柱子为高度往两边延申的边界，要作为柱子的边界就必须高度不能低于该柱子，否则矩形无法同高，也就是需要找出以每根柱子为高、往两边找更低的柱子作为当前矩形的边界（不含）

可以用一个单调递增栈，存储下标，一直记录更高的柱子，一旦碰到低的柱子，此时栈顶可作为矩形的高，当前柱子作为右边界（不含），栈顶往下一个元素可作为左边界（不含），计算完成后弹出栈顶，这样可以以每个柱子的高度为矩形的高计算一次面积，且边界都是尽可能延申的

class Solution {
public:
    int largestRectangleArea(vector<int> &heights) {
        int ans = 0;
        heights.insert(heights.begin(), 0); // 尾哨兵
        heights.push_back(0); // 头哨兵
        stack<int> 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;
    }
};

本文参与?腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2024-04-07，如有侵权请联系 cloudcommunity@tencent.com 删除

存储