代码随想录算法训练营第60天 | 84.柱状图中最大的矩形

84.柱状图中最大的矩形

代码随想录链接

题目

LeetCode-84.柱状图中最大的矩形

给定一系列柱状图中依次相邻柱子的高度, 求这些柱子能勾勒出的最大的矩形的面积.

题目分析

和昨天LeetCode-42.接雨水非常相似.

双指针

在LeetCode-42.接雨水的双指针法中, 遍历的每个柱子是为了求当前柱子上能积多少水. 而本题目中, 是要求以每根柱子的高度为高, 与两侧的柱子能形成的最大面积, 这就要求找到每根柱子两侧连续且不低于自身高度的柱子的范围, 这样才能求得最大面积.

和LeetCode-42.接雨水类似, 先标记每根柱子左侧最近的高度低于自身的柱子, 再标记每根柱子右侧最近的高度低于自身的柱子, 这样就确定了以自身高度为高, 左右两个高度低于自身的柱子中间的部分为宽的矩形.

单调栈

与上面分析的思路类似, 单调栈中应该从栈顶到栈底是递减顺序, 这样能保证在遇到比栈顶小的元素时, 将栈内的元素进行类似于上面的求面积操作.

题解

双指针:

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        vector<int> minLeftIndexes(heights.size());
        vector<int> minRightIndexes(heights.size());

        minLeftIndexes[0] = -1; // 统计每根柱子左侧最近且低于自己的柱子
        for (int i = 1; i < heights.size(); i++) {
            int t = i - 1;
            while (t >= 0 && heights[t] >= heights[i])
                t = minLeftIndexes[t];
            minLeftIndexes[i] = t;
        }

        minRightIndexes.back() = heights.size(); // 统计每根柱子右侧最近且低于自己的柱子
        for (int i = heights.size() - 1; i >= 0; i--) {
            int t = i + 1;
            while (t < heights.size() && heights[t] >= heights[i])
                t = minRightIndexes[t];
            minRightIndexes[i] = t;
        }

        int result = 0; // 求左右两侧高于等于自己的柱子以自己的高所能形成的面积
        for (int i = 0; i < heights.size(); i++) {
            int sum = heights[i] * (minRightIndexes[i] - minLeftIndexes[i] - 1);
            result = max(sum, result);
        }
        return result;
    }
};

单调栈:

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int result = 0;
        stack<int> st;
        heights.insert(heights.begin(), 0);
        heights.push_back(0);
        st.push(0);

        for (int i = 1; i < heights.size(); i++) {
            if (heights[i] >= heights[st.top()]) {
                st.push(i);
            } else {
                while (!st.empty() && heights[i] < heights[st.top()]) {
                    int mid = st.top();
                    st.pop();
                    if (!st.empty()) {
                        int left = st.top();
                        int right = i;
                        int w = right - left - 1;
                        int h = heights[mid];
                        result = max(result, w * h);
                    }
                }
                st.push(i);
            }
        }
        return result;
    }
};