# Use Segment Tree causes StackOverFlow error. How to fix it?

``````public int largestRectangleArea(int[] heights) {
if (heights.length == 0) {
return 0;
}
SegmentTree st = new SegmentTree(heights);
return largestRectangleArea(heights, 0, heights.length - 1, st);
}
private int largestRectangleArea(int[] heights, int left, int right, SegmentTree st) {
if (left > right) {
return Integer.MIN_VALUE;
} else if (left == right) {
return heights[left];
} else {
int min = st.getMin(left, right); // min index
return Math.max(Math.max(largestRectangleArea(heights, left, min - 1, st), largestRectangleArea(heights, min + 1, right, st)), heights[min] * (right - left + 1));
}
}
private class SegmentTree { // Range Minimum Query
private int[] st; // each element is min index of the range
private int[] array;
private int n;
// constructor
public SegmentTree(int[] array) {
this.array = array;
this.n = array.length;
int h = (int) Math.ceil(Math.log(n) / Math.log(2));
this.st = new int[(2 << h) - 1];
constructST(0, n - 1, 0);
}
private int constructST(int left, int right, int index) { // left&right is range in array[]. index is st[].
if (left == right) {
st[index] = left;
} else {
int mid = (left + right) / 2;
int minLeft = constructST(left, mid, 2 * index + 1);
int minRight = constructST(mid + 1, right, 2 * index + 2);
st[index] = array[minLeft] < array[minRight] ? minLeft : minRight;
}
return st[index];
}
// get Minimum index of given range. qs is query start, qe is query end. return index of the min
public int getMin(int qs, int qe) {
if (qs < 0 || qe >= n || qe < qs) {
return -1;
} else {
return getMin(qs, qe, 0, n - 1, 0);
}
}
private int getMin(int qs, int qe, int ss, int se, int si) { // ss&se is st[] start&end, si is st[] index
if (qs > se || qe < ss) { // out of range
return -1;
} else if (qs <= ss && qe >= se) { // st[] range is in query range
return st[si];
} else {
int mid = (ss + se) / 2;
int minLeft = getMin(qs, qe, ss, mid, 2 * si + 1);
int minRight = getMin(qs, qe, mid + 1, se, 2 * si + 2);
if (minLeft == -1) {
return minRight;
} else if (minRight == -1) {
return minLeft;
} else {
return array[minLeft] < array[minRight] ? minLeft : minRight;
}
}
}
}``````

• Same here for cases like [1,2,3,4,...,1000000]. I guess iterative solution might solve this but I haven't tried.

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