Segment tree solution, just another idea, O(N*logN) Solution
Inspired by this solution:\nhttp://www.geeksforgeeks.org/largest-rectangular-area-in-a-histogram-set-1/\n\nJust wanna to provide another idea of how to solve th
Inspired by this solution:\nhttp://www.geeksforgeeks.org/largest-rectangular-area-in-a-histogram-set-1/\n\nJust wanna to provide another idea of how to solve this question in O(N*logN) theoretically, 40 ms solution:\n\n    // Largest Rectangle in Histogram\n    // Stack solution, O(NlogN) solution\n    \n    class SegTreeNode {\n    public:\n      int start;\n      int end;\n      int min;\n      SegTreeNode *left;\n      SegTreeNode *right;\n      SegTreeNode(int start, int end) {\n        this->start = start;\n        this->end = end;\n        left = right = NULL;\n      }\n    };\n    \n    class Solution {\n    public:\n      int largestRectangleArea(vector<int>& heights) {\n        if (heights.size() == 0) return 0;\n        // first build a segment tree\n        SegTreeNode *root = buildSegmentTree(heights, 0, heights.size() - 1);\n        // next calculate the maximum area recursively\n        return calculateMax(heights, root, 0, heights.size() - 1);\n      }\n      \n      int calculateMax(vector<int>& heights, SegTreeNode* root, int start, int end) {\n        if (start > end) {\n          return -1;\n        }\n        if (start == end) {\n          return heights[start];\n        }\n        int minIndex = query(root, heights, start, end);\n        int leftMax = calculateMax(heights, root, start, minIndex - 1);\n        int rightMax = calculateMax(heights, root, minIndex + 1, end);\n        int minMax = heights[minIndex] * (end - start + 1);\n        return max( max(leftMax, rightMax), minMax );\n      }\n      \n      SegTreeNode *buildSegmentTree(vector<int>& heights, int start, int end) {\n        if (start > end) return NULL;\n        SegTreeNode *root = new SegTreeNode(start, end);\n        if (start == end) {\n            root->min = start;\n          return root;\n        } else {\n          int middle = (start + end) / 2;\n          root->left = buildSegmentTree(heights, start, middle);\n          root->right = buildSegmentTree(heights, middle + 1, end);\n          root->min = heights[root->left->min] < heights[root->right->min] ? root->left->min : root->right->min;\n          return root;\n        }\n      }\n      \n      int query(SegTreeNode *root, vector<int>& heights, int start, int end) {\n        if (root == NULL || end < root->start || start > root->end) return -1;\n        if (start <= root->start && end >= root->end) {\n          return root->min;\n        }\n        int leftMin = query(root->left, heights, start, end);\n        int rightMin = query(root->right, heights, start, end);\n        if (leftMin == -1) return rightMin;\n        if (rightMin == -1) return leftMin;\n        return heights[leftMin] < heights[rightMin] ? leftMin : rightMin;\n      }\n    };
['C++']