I use a sparse table to store min value of intervals, then I use O(nlogn) "divide and concur" to solve it.
However, I still got TLE error.
Does any one try sparse table or interval tree and got an AC?
Can you share your code?
Thank you !
Does any one got an AC using sparse table.

I believe using sparse table or interval tree is a way to solve this problem.
Take a look at this answer. It might broaden your horizon.

The idea is to find the base bar which gives the maximum area. Lowest bar is the option, divided by the lowest bar, the original vector is divided into 3 sections, [leftSide, lowestbar, rightSide], Recursively call leftSide and RightSide.
Since find lowest Bar is O(n) generally, T(n) = T(k1) + T(nk) + n, in the worst case, T(n) = n^2, in order to optimise the performance to O(nlogn), segment tree is a good option since it costs O(n) construction and O(logn) query.
The following is my Ac code, please feel free to comment it.
class Solution { public: void buildMinRange(const vector<int>& height, int b, int e, int node, vector<int>& M) { if(b == e) M[node] = b; else { int mid = b + (eb)/2; buildMinRange(height, b, mid, node*2, M); buildMinRange(height, mid+1, e, node*2+1, M); if(height[M[node*2]] <= height[M[node*2+1]]) M[node] = M[node*2]; else M[node] = M[node*2+1]; } } int findMin(int i, int j, const vector<int>& height, int node, int b, int e, const vector<int>& M) { if(j < b  i > e) return 1; if(i<= b && j >= e) return M[node]; int mid = b + (eb)/2; int p = findMin(i, j, height, node*2, b, mid, M); int q = findMin(i, j, height, node*2+1, mid+1, e, M); if(p == 1) return q; if(q == 1) return p; if(height[p] <= height[q]) return p; else return q; } int largestRectangleArea(int i, int j, const vector<int>& height, const vector<int>& M) { if(i > j) return 0; if( i == j) return height[i]; int lowest = findMin(i, j, height, 1, 0, height.size()1, M); int area = height[lowest]*(ji+1); int leftArea = largestRectangleArea(i, lowest1, height, M); int rightArea = largestRectangleArea(lowest+1, j, height, M); return max(area, max(leftArea, rightArea)); } int largestRectangleArea(vector<int> &height) { if(height.empty()) return 0; int sz = height.size(); int h = ceil(log2(sz)); vector<int> M(1<<(h+1), 1); buildMinRange(height, 0, sz1, 1, M); return largestRectangleArea(0, sz1, height, M); } };