Share my C++ solution using array,easy to understand


  • 0
    V
    class Solution {
    public:
        int largestRectangleArea(vector<int>& heights) {
            int n = heights.size();
            if (n == 0)
                return 0;
            
            vector<int> bar(n, 0);
            bar[0] = heights[0];
            int max_area = bar[0];
            int len = 1;
            int i = 1;
            int cur_area = 0;
            int cnt = 0;
            
            while (i < n)
            {
                if (heights[i] >= bar[len-1])
                {
                    bar[len++] = heights[i++];
                }
                else
                {
                    int j = len-1;
                    cur_area = 0;
                    cnt = 0;
                    while (j >= 0 && heights[i] < bar[j])
                    {
                        cnt++;
                        cur_area = bar[j] * cnt;
                        if (max_area < cur_area)
                            max_area = cur_area;
                    
                        j--;
                    }
                    
                    for (int k = j+1; k < len; k++)
                        bar[k] = heights[i];
                }
            }
            
            cnt = 0;
            cur_area = 0;
            for (int k = len - 1; k >= 0 ;k--)
            {
                cnt++;
                cur_area = bar[k] * cnt;
                if (max_area < cur_area)
                    max_area = cur_area;
            }
            
            return max_area;
        }
    };
    

Log in to reply
 

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