# C++ two methods : O(NlogN) and O(N)

• ``````class Solution {
public:
//O(NLogN) divide and conquer,
//using segment tree to find range minmum
int getMin(vector<int>& hist, int i, int j) {
if (i == -1) return j;
if (j == -1) return i;
return (hist[i] < hist[j]) ? i : j;
}
int RMQUtil(vector<int>& hist, vector<int>& st, int ss, int se, int qs, int qe, int index)
{
if (se < qs || ss > qe) {
return -1;
}
else if (qs <= ss && qe >= se) {
return st[index];
}
int mid = ss + (se - ss) / 2;
int left = RMQUtil(hist, st, ss, mid, qs, qe, 2 * index + 1);
int right = RMQUtil(hist, st, mid + 1, se, qs, qe, 2 * index + 2);
return getMin(hist, left, right);
}
int constructSTUtil(vector<int>& hist, int ss, int se, vector<int>& st, int si)
{
if (ss == se) {
return (st[si] = ss);
}
int mid = ss + (se - ss) / 2;
int left = constructSTUtil(hist, ss, mid, st, si * 2 + 1);
int right = constructSTUtil(hist, mid + 1, se, st, si * 2 + 2);
st[si] = getMin(hist, left, right);
return st[si];
}
vector<int> constructST(vector<int>& hist, int n)
{
int x = (int)(ceil(log2(n)));
int max_size = 2 * (int)pow(2, x) - 1;
vector<int> st(max_size, 0);
constructSTUtil(hist, 0, n - 1, st, 0);
return st;
}
int recur(int left, int right, vector<int>& heights, vector<int>& st) {
if (left > right) {
return INT_MIN;
}
else if (left == right) {
return heights[left];
}

int minIdx = RMQUtil(heights, st, 0, heights.size() - 1, left, right, 0);
/* the linear search will cause TLE
int minValue = INT_MAX;
int minIdx = -1;
for(int i = left; i <= right; ++i){
if(heights[i] < minValue){
minValue = heights[i];
minIdx = i;
}
}*/
int leftMin = recur(left, minIdx - 1, heights, st);// it's max , the name is misleading, sorry
int rightMin = recur(minIdx + 1, right, heights, st);
return max(max(leftMin, rightMin), heights[minIdx] * (right - left + 1));

}
int largestRectangleArea(vector<int>& heights) {
int len = heights.size();
if (len == 0) {
return 0;
}
vector<int> st = constructST(heights, len);
return recur(0, len - 1, heights, st);
}
//O(N) stack
/*
int largestRectangleArea(vector<int>& heights) {
int ans = 0;
int len = heights.size();
if(len == 0){
return 0;
}
stack<int> st;
for(int i = 0; i <= len;){
int h = (i == len ? 0 : heights[i]);
if(st.empty() || heights[st.top()] <= h){
st.push(i++);
}else{
int tmp = st.top();
st.pop();
int l = (st.empty() ? i : i - st.top() - 1);
ans = max(ans, l * heights[tmp]);
}
}
return ans;
}
*/
};``````

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