26 Dec 2016

Recursion to divide and conquer I

文章欢迎转载,但转载时请保留本段文字,并置于文章的顶部
Author: derek0883@gmail.com
本文原文地址:http://www.gorecursion.com/algorithm/2016/12/26/div-con1.html

This example will show you how to use recursion method solve problem, then lead to two Divide and Conquer solution.

Largest Rectangle in Histogram

Leetcode Largest Rectangle in Histogram

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.

Histogram

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

Histogram

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example, Given heights = [2,1,5,6,2,3], return 10.

Video explanation

Brute force

It is very easy to comeup with a brute force solution, Just examine each possible combination start and end.

Divide and Conquer – Eager version of brute force

private int divideAndconquer(int[] heights, int L, int R) {
    if (L > R)
        return 0;

    int M = getMinIndex(heights, L, R);
    int area = heights[M] * (R-L+1);
    int leftArea = largestRectangleArea(heights, L, M-1, minIdx);
    int rightArea = largestRectangleArea(heights, M+1, R, minIdx);

    area = Math.max(leftArea, area);
    area = Math.max(rightArea, area);
    return area;
}

Find minimal index in a given range

Brute force solution would be scan from left to right one by one, overall time complexity would be O(n*lgN) * O(n), it is O(n^2 lgN)

It is very easy to come up with a two dimensional dynamic programing solution. It takes O(n^2) time to build DP table, and O(1) time return minimal index in given range. The time complexity of Divide and Conquer is O(n*lg(n)), build DP table for minimal range query is O(n^2). So overall time complexity is O(n^2).

public class Solution {
    int[][] minIdx;
    public int largestRectangleArea(int[] heights) {
        buildMinIndex(heights);
        return divideAndConquer(heights, 0, heights.length-1);
    }

    private void buildMinIndex(int[] heights) {
        int n = heights.length;
        minIdx = new int[n][n];

        // Build minIdx arrary using DP
        for (int i = 0; i < n; i++)
            minIdx[i][i] = i;
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n-len; i++) {
                int j = i+len-1;
                if (heights[j] < heights[minIdx[i][j-1]])
                    minIdx[i][j] = j;
                else
                    minIdx[i][j] = minIdx[i][j-1];
            }
        }
    }

    private int getMinIndex(int L, int R) {
        return minIdx[L][R];
    }
}

Segment tree

The bottleneck of above solution is minimal range qeury. Both time complexity and space complexity is O(n^2). With segment tree, we can build the tree in O(n) time, and takes O(lg n) time for each query. Segment tree is not the topic of this post, you can watch this video if you don’t understand segment tree.

Overall time complexity is O(n*lg n). In term of time efficiency, this is good enough to pass leetcode onlie OJ. But the problem is stack, As both segment tree query and divide and conquer functions are recursvie call,

If you copy the input to local, and test with “-Xss4m”, this will change default stack size to 4M. you will see it is real fast.

"time java -Xss4m LargestRectangleArea" 

Following code are divide and conquer solution. If you are not familiar with segment tree, you can ignore it for now, focus on this problem. you should understand divide and conquer part of the following code before you move to next section. I show you how to optimize it further.

public class Solution {
    class Node {
        Node left, right;
        int index, start, end;
        Node(int i, int s, int e) { index = i; start = s; end = e; }
    }

    Node root;

    public int largestRectangleArea(int[] heights) {
        root = buildSegmentTree(heights, 0, heights.length-1);
        return divideAndConquer(heights, 0, heights.length-1);
    }
    private int divideAndConquer(int[] heights, int L, int R) {
        if (L > R)
            return 0;
    
        int M = getMinIndex(heights, root, L, R);
        int area = heights[M] * (R-L+1);
        int leftArea = divideAndConquer(heights, L, M-1);
        int rightArea = divideAndConquer(heights, M+1, R);
    
        area = Math.max(leftArea, area);
        area = Math.max(rightArea, area);
        return area;
    }

    Node buildSegmentTree(int[] heights, int L, int R) {
        if (L > R)
            return null;
        if (L == R)
            return new Node(L, L, L);
        int M = (R-L)/2 + L;
        Node left = buildSegmentTree(heights, L, M);
        Node right = buildSegmentTree(heights, M+1, R);
        Node root;
        int i;
        if (left == null)
            i = right.index;
        else if (right == null)
            i = left.index;
        else
            i = heights[right.index] < heights[left.index] ? right.index : left.index;
        root = new Node(i, L, R);
        root.left = left;
        root.right = right;
        return root;
    }
    private int getMinIndex(int[] heights, Node root, int L, int R) {
        if (root == null)
            return -1;
        if (L <= root.start && R >= root.end)
            return root.index;
        if (L > root.end || R < root.start)
            return -1;
        int l = getMinIndex(heights, root.left, L, R);
        int r = getMinIndex(heights, root.right, L, R);
        if (l == -1)
            return r;
        if (r == -1)
            return l;
        return heights[l] < heights[r] ? l : r;
    }
}

Further Optimization

For divide and conquer, ideally we want divide it at middle, the size of two sub problems are relatively same. But if a range is monotonic increase or decrease, each time we will get minimal index either on the left side or on the right side. That’s “hurt” divide and conquer solution. That’s why above solution can’t pass leetcode OJ.

For this problem, monotonic increase or decrease actually reduced the complexity, for such input we can finish it in O(n) time. Here is simple change to divide and conquer, it passed leetcode OJ, Runtime: 17 ms. As you can see this simple change makes big difference. Be able to solve the problem and not be able to solve the problem.

The idea is simple, when get minimal index on left side or right side, we calculate the area for that index, then adjust L or R index accordingly. If you don’t understand, you should watch above video.

private int divideAndConquerV2(int[] heights, int L, int R) {
    if (L > R)
        return 0;

    int area = 0;
    int M = getMinIndex(heights, root, L, R);
    while (L <= R && (M == L || M == R)) {
        area = Math.max(area, heights[M] * (R-L+1));
        if (M == L)
            L++;
        else if (M == R)
            R--;
        M = getMinIndex(heights, root, L, R);
    }

    if (R < L)
        return area;
    area = Math.max(area, heights[M] * (R-L+1));
    int leftArea = divideAndConquerV2(heights, L, M-1);
    int rightArea = divideAndConquerV2(heights, M+1, R);
    area = Math.max(leftArea, area);
    area = Math.max(rightArea, area);
    return area;
}