题解 | 柱状图中的最大矩形

题目:

题干解析:

题目给定n个非负整数,假设有n个宽度为1,高度为heights[i]的矩形拼接在一起,题目要求我们返回能够完全被覆盖的矩形的最大值.

首先我们证明这个矩形的高一定是heights中的一个元素,因为如果不是那么要让其完全被覆盖其高度一定就小于height,因此存在另一个矩形,其高度就是height宽度与其相同,则该矩形面积会更大,因此符合题意的矩形高度一定为height数组中的一个元素.

算法思路:

本题其实有三种解决方法,分别为一,二,三次遍历实现,目前我只弄懂了三次遍历实现的方法,因此只讲解此方法.

我们已知符合题意得矩形高度一定为数组中的一个元素,因此我们遍历整个数组针对每个元素进行操作即可获得最大值.同时我们不难理解,要使这个矩形最大,我们只需要找到左起第一个与右起第一个小于该数组元素的元素索引即可,该矩形最大宽度即为两索引相减再减一.

现在问题转化为如何求得从数组中某个元素出发左起与右起第一个小于其的数组索引.已知我们使用单调栈一次循环能够完成一边(左起或右起)的索引发现,我们直接进行两次遍历即可获得两个索引值,此后就如同之前所说,遍历数组获取矩形面积最大值即可.

实现代码:

int largestRectangleArea(vector<int> &heights) {
        stack<int> st;
        const int n = static_cast<int>(heights.size());
        vector<pair<int, int> > range(n, {-1, n});

        // 首次遍历
        st.push(0);
        for (int i = 1; i < n; ++i) {
            if (heights[i] >= heights[st.top()]) st.push(i);
            else {
                while (!st.empty() && heights[i] < heights[st.top()]) {
                    range[st.top()].second = i;
                    st.pop();
                }
                st.push(i);
            }
        }
        while (!st.empty()) {
            range[st.top()].second = n;
            st.pop();
        }

        // 二次遍历
        st.push(n - 1);
        for (int i = n - 2; i != -1; --i) {
            if (heights[i] >= heights[st.top()]) st.push(i);
            else {
                while (!st.empty() && heights[i] < heights[st.top()]) {
                    range[st.top()].first = i;
                    st.pop();
                }
                st.push(i);
            }
        }
        while (!st.empty()) {
            range[st.top()].first = -1;
            st.pop();
        }

        // 三次遍历
        int _max = 0;
        for (int i = 0; i < n; ++i) _max = max(_max, heights[i] * (range[i].second - range[i].first - 1));

        return _max;
    }

复杂度分析:

针对n个正整数:

总计进行三次遍历,每次遍历针对数组元素进行操作花费常数的时间,因此时间复杂度为O(n);

每个元素最坏情况下均得进栈,且需要O(n)的额外空间存储索引值,因此空间复杂度为O(n).