LC: Largest Rectangle in Histogram

84. Largest Rectangle in Histogram

TLE O(n²)

This TLE solution is not that bad, it got 95 / 96 test cases passed.

const int INF = INT_MAX;
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        const int n = heights.size();
        int ret = 0;
        for (int i = 0; i < n; ++i) {
            int minv = INF;
            for (int j = i; j < n; ++j){
                minv = min(minv, heights[j]);
                ret = max(ret, minv*(j - i + 1));
            }
        }
        return ret;
    }
};

O(n)

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        heights.push_back(0);
        const int n = heights.size();
        int ret = 0;
        stack<int> indexes;
        int h, l;
        for (int i = 0; i < n; i++) {
            while (!indexes.empty() && heights[indexes.top()] > heights[i]) {
                h = heights[indexes.top()]; indexes.pop();
                l = indexes.empty() ? -1 : indexes.top();
                ret = max(ret, h * (i - l - 1));
            }
            indexes.push(i);
        }
        return ret;
    }
};

Reference

[1]https://leetcode.com/problems/largest-rectangle-in-histogram/discuss/28905/My-concise-C++-solution-AC-90-ms/27790

[2]https://leetcode.com/problems/largest-rectangle-in-histogram/discuss/28905/My-concise-C%2B%2B-solution-AC-90-ms