LeetCode——Largest Rectangle in Histogram

Question

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,

Given heights = [2,1,5,6,2,3],

return 10.

Solution 1

动态规划，但是会超时。

Code 1

class Solution {

public:

    int largestRectangleArea(vector<int>& heights) {

        int num = heights.size();

        if (num == 0)

            return 0;

        vector<vector<int>> min_heights(num, vector<int>(num, 0));

        vector<vector<int>> max_areas(num, vector<int>(num, 0));

        for (int i = 0; i < num; i++) {

            min_heights[i][i] = heights[i];

            max_areas[i][i] = heights[i] * 1;

        }

        for (int i = 2; i <= num; i++) {

            for (int j = 0; j <= num - i; j++) {

                min_heights[j][j + i - 1] = min(heights[j], min_heights[j + 1][j + i - 1]);

                max_areas[j][j + i - 1] = max(min_heights[j][j + i - 1] * i, max_areas[j + 1][j + i - 1]);

                max_areas[j][j + i - 1] = max(max_areas[j][j + i - 1], max_areas[j][j + i - 2]);

            }

        }

        return max_areas[0][num - 1];

    }

};

Solution 2

同样是动态规划，但是这次只需要记录之前的比自己低的坐标值。然后遍历之前比自己低的坐标值，每个低的都计算一次面积，具体看代码实现。

Code 2

class Solution {

public:

    int largestRectangleArea(vector<int> &height) {

        // 记录比自己低的index

        int res = 0;

        height.push_back(0);

        vector<int> index;

        for (int i = 0; i < height.size(); i++) {

            // 遍历所有比当前高度高的值，这也就是为什么会在height后面插入0的原因

            while (index.size() > 0 && height[index.back()] >= height[i]) {

                int h = height[index.back()];

                index.pop_back();

                // 这个是为了计算宽度值

                int idx = index.size() > 0 ? index.back() : -1;

                if (h * (i - idx - 1) > res)

                    res = h * (i - idx - 1);

            }

            index.push_back(i);

        }

        return res;

    }

};

巴特西