Simple Divide and Conquer AC solution without Segment Tree
The idea is simple: for a given range of bars, the maximum area can either from left or right half of the bars, or from the area containing the middle two bars.
The idea is simple: for a given range of bars, the maximum area can either from left or right half of the bars, or from the area containing the middle two bars. For the last condition, expanding from the middle two bars to find a maximum area is `O(n)`, which makes a typical Divide and Conquer solution with `T(n) = 2T(n/2) + O(n)`. Thus the overall complexity is `O(nlgn)` for time and `O(1)` for space (or `O(lgn)` considering stack usage). \n\nFollowing is the code accepted with 44ms. I posted this because I didn't find a similar solution, but only the RMQ idea which seemed less straightforward to me.\n\n    class Solution {\n        int maxCombineArea(const vector<int> &height, int s, int m, int e) {\n            // Expand from the middle to find the max area containing height[m] and height[m+1]\n            int i = m, j = m+1;\n            int area = 0, h = min(height[i], height[j]);\n            while(i >= s && j <= e) {\n                h = min(h, min(height[i], height[j]));\n                area = max(area, (j-i+1) * h);\n                if (i == s) {\n                    ++j;\n                }\n                else if (j == e) {\n                    --i;\n                }\n                else {\n                    // if both sides have not reached the boundary,\n                    // compare the outer bars and expand towards the bigger side\n                    if (height[i-1] > height[j+1]) {\n                        --i;\n                    }\n                    else {\n                        ++j;\n                    }\n                }\n            }\n            return area;\n        }\n        int maxArea(const vector<int> &height, int s, int e) {\n            // if the range only contains one bar, return its height as area\n            if (s == e) {\n                return height[s];\n            }\n            // otherwise, divide & conquer, the max area must be among the following 3 values\n            int m = s + (e-s)/2;\n            // 1 - max area from left half\n            int area = maxArea(height, s, m);\n            // 2 - max area from right half\n            area = max(area, maxArea(height, m+1, e));\n            // 3 - max area across the middle\n            area = max(area, maxCombineArea(height, s, m, e));\n            return area;\n        }\n    public:\n        int largestRectangleArea(vector<int> &height) {\n            if (height.empty()) {\n                return 0;\n            }\n            return maxArea(height, 0, height.size()-1);\n        }\n    };
['Divide and Conquer', 'C++']