Max Area Problems (Input Array and Calculate Maximum Area by Some Conditions)

Algorithm

Such problems typically provides an array presenting the height in its index, and calculate the maximum area according to some comparsion of heights.
There are pretty amount ways to address these problem. Basically, they can be firgured out by two pointer (similar with binary search or two sum; two-passing with some mark or additional array space; stack)

1. Contain Most Water

思路有点类似于Two Sum中的第二种方法--夹逼。从数组两端走起，每次迭代时判断左pointer和右pointer指向的数字哪个大，如果左pointer小，意味着向左移动右pointer不可能使结果变得更好，因为瓶颈在左pointer，移动右pointer只会变小，所以这时候我们选择左pointer右移。反之，则选择右pointer左移。在这个过程中一直维护最大的那个容积.

public int maxArea(int[] height) {
        int l = 0;
        int r = height.length - 1;
        int maxArea = 0;
        while (l < r) {
            int curArea = Math.min(height[l], height[r]) * (r - l);
            maxArea = Math.max(maxArea, curArea);
            if (height[l] < height[r])
                l++;
            else
                r--;
        }
        return maxArea;
    }

2. Largest Rectangle in Histogram

    public int largestRectangleArea(int[] height) {
        if (height == null || height.length == 0)
            return 0;
        Stack<Integer> stack = new Stack<Integer>();
        int maxArea = 0;
        height = Arrays.copyOf(height, height.length + 1);
        for (int i = 0; i < height.length; i++) {
            while(!stack.isEmpty()&&height[i]<=height[stack.peek()]){
                // compare current element and stack top element
                int prevIdx = stack.pop();
                int curArea = (stack.isEmpty()?i:(i-stack.peek()-1))*height[prevIdx];
                // the height should be referenced to previous first index
                // the width should be referenced to stack top element
                maxArea = Math.max(maxArea, curArea);
            }
            stack.push(i);
        }
        return maxArea;
    }

一个细节需要注意的是，弹栈过程中面积的计算。

h[t] * (stack.isEmpty() ? i : i - stack.peek() - 1)

h[t]是刚刚弹出的栈顶端元素。此时的面积计算是h[t]和前面的“上流社会”能围成的最大面积。这时候要注意哦，栈内索引指向的元素都是比h[t]小的，如果h[t]是目前最小的，那么栈内就是空哦。而在目前栈顶元素和h[t]之间（不包括h[t]和栈顶元素），都是大于他们两者的。如下图所示：

那h[t]无疑就是Stack.Peek和t之间那些上流社会的短板啦，而它们的跨越就是i - Stack.Peek - 1。

3. Trapping Rain Water

Two passing ways. First passing to record the left max in additional array then update this array in second passing(rear -> front) which get the right max and Math.min(left(original element in current index of array), right), finally, get the difference between container[i] and A[i];

    public static int trap(int[] A) {
        if (A == null || A.length == 0)
            return 0;
        int[] container = new int[A.length];
        container[0] = 0;
        int leftMax = A[0];
        for (int i = 1; i < A.length; i++) {
            container[i] = leftMax;
            leftMax = Math.max(leftMax, A[i]);
        }
        int res = 0;
        int rightMax = A[A.length - 1];
        for (int i = A.length - 2; i >= 0; i--) {
            container[i] = Math.min(container[i], rightMax);
            rightMax = Math.max(rightMax, A[i]);
            res += ((container[i] - A[i]) > 0 ? (container[i] - A[i]) : 0);
        }
        return res;
    }

4. Maiximal Rectangle

Each line can be regarded as a histogram;
0 0 0 0 1 0
0 0 1 1 1 1
0 0 0 1 1 1
0 0 0 1 1 0

------>>>>>

0 0 0 0 1 0
0 0 1 1 2 1
0 0 0 2 3 2
0 0 0 3 4 0

Then follow the same procedure as Histrogram：

private int maximalRectStackWay(char[][] matrix) {
        if (matrix == null || matrix.length == 0)
            return 0;
        int colLen = matrix[0].length;
        int rowLen = matrix.length;
        int maxArea = 0;
        int[] rowHeight = new int[colLen + 1]; // keep current line as histogram
        Stack<Integer> stack;
        for (int row = 0; row < matrix.length; row++) {
            stack = new Stack<Integer>();
            for (int col = 0; col <= matrix[0].length; col++) {
                if (col < matrix[0].length && matrix[row][col] == '1')
                    rowHeight[col]++;
                else
                    rowHeight[col] = 0;
                /******* Histogram Method ************/
                while (!stack.isEmpty()
                        && rowHeight[col] <= rowHeight[stack.peek()]) {
                    int prevIdx = stack.pop();
                    int curArea = (stack.isEmpty() ? col
                            : (col - stack.peek() - 1)) * (rowHeight[prevIdx]);
                    maxArea = Math.max(maxArea, curArea);
                }
                stack.push(col);
                /**********************************/
            }
        }
        return maxArea;
}