LeetCode(84) -- Largest Rectangle in Histogram (Segment Tree)

Problem

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Solution

方法四：线段树

线段树是用一个完全二叉树来存储对应于其每一个区间（segment）的数据

class Solution {
    
    class SegTreeNode {
        int start;
        int end;
        int min;
        SegTreeNode left;
        SegTreeNode right;
        public SegTreeNode(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }
    
    public int largestRectangleArea(int[] heights) {
        if (heights.length == 0) {
            return 0;
        }
        SegTreeNode root = buildSegmentTree(heights, 0, heights.length - 1);
        
        return calculateMax(heights, root, 0, heights.length - 1);
    }
    
    public int calculateMax(int[] heights, SegTreeNode root, int start, int end) {
        if (start > end) {
            return -1;
        }
        if (start == end) {
            return heights[start];
        }
        int minIndex = query(root, heights, start, end);
        int leftMax = calculateMax(heights, root, start, minIndex - 1);
        int rightMax = calculateMax(heights, root, minIndex + 1, end);
        int minMax = heights[minIndex] * (end - start + 1);
        return Math.max(Math.max(leftMax, rightMax), minMax);
    }
    
    public SegTreeNode buildSegmentTree(int[] heights, int start, int end) {
        if (start > end) return null;
        SegTreeNode root = new SegTreeNode(start, end);
        if (start == end) {
            root.min = start;
            return root;
        } else {
            int middle = (start + end) / 2;
            root.left = buildSegmentTree(heights, start, middle);
            root.right = buildSegmentTree(heights, middle + 1, end);
            root.min = heights[root.left.min] < heights[root.right.min] ? root.left.min : root.right.min;
            return root;
        }
    }
    
    public int query(SegTreeNode root, int[] heights, int start, int end) {
        if (root == null || end < root.start || start > root.end) return -1;
        if (start <= root.start && end >= root.end) {
            return root.min;
        }
        int leftMin = query(root.left, heights, start, end);
        int rightMin = query(root.right, heights, start, end);
        if (leftMin == -1) return rightMin;
        if (rightMin == -1) return leftMin;
        return heights[leftMin] < heights[rightMin] ? leftMin : rightMin;
    }
}