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


  • 0
    D

    Anyone please help figure this out? Thank you so much.

    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;
    			}
    		}
    	}
    }

  • 0
    S

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


Log in to reply
 

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