10 line c++ solution


  • 7
    K
    class Solution {
    public:
        int largestRectangleArea(vector<int>& heights) {
            int res = 0;
            for (int i = 0; i < heights.size(); ++i) {
                if (i + 1 < heights.size() && heights[i] <= heights[i+1]) continue; // find the local max (greater than left and right)
                int minh = heights[i];
                for (int j = i; j >= 0; --j) {
                    minh = min(minh, heights[j]);
                    res = max(res, minh * (i - j + 1));
                }
            }
            return res;
        }
    };

  • 0
    K

    Can you tell its time complexity? I think its O(n^2). Correct me if I am wrong.


  • 0
    K

    when heights is decreasing order, worst case yes


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.