Trapping Rain Water

 基本思路是这样的，用两个指针从两端往中间扫，在当前窗口下，如果哪一侧的高度是小的，那么从这里开始继续扫，如果比它还小的，肯定装水的瓶颈就是它了， 可以把装水量加入结果，如果遇到比它大的，立即停止，重新判断左右窗口的大小情况，重复上面的步骤。这里能作为停下来判断的窗口，说明肯定比前面的大了， 所以目前肯定装不了水（不然前面会直接扫过去）。这样当左右窗口相遇时，就可以结束了，因为每个元素的装水量都已经记录过了。代码如下：
int trap(int A[], int n) {
    int i = 0, j = n-1;
    int volume = 0;       
    int k = 0;
    while (i < j) {
        if (A[i] <= A[j]) {
            k = i+1;
            while (A[i] > A[k]) {
                volume += (A[i]-A[k]);
                k++;
            }
            i = k;
        }
        else {
            k = j-1;
            while (A[j] > A[k]) {
                volume += (A[j]-A[k]);
                k--;
            }
            j = k;
        }
    }  
    return volume;       
}


//method 2, by anniekim.
DP solution: Find left bound and right bound for each element. O(n).

int trap(int A[], int n) {
    if (n == 0) return 0;
    vector<int> maxLeft(n,0);
    vector<int> maxRight(n,0);
    maxLeft[0] = A[0];
    maxRight[n - 1] = A[n - 1];
    for (int i = 1; i < n; ++i) {
        maxLeft[i] = max(maxLeft[i - 1], A[i]);
        maxRight[n - 1 - i] = max(maxRight[n - i], A[n - 1 - i]);
    }
    int res = 0;
    for (int i = 1; i < n; ++i) {
        res += min(maxLeft[i], maxRight[i]) - A[i];
    }
    return res;
}

Code Ganker: Binary Tree Zigzag Level Order Traversal -- LeetCo...

Code Ganker: Binary Tree Zigzag Level Order Traversal -- LeetCo...: 原题链接: http://oj.leetcode.com/problems/binary-tree-zigzag-level-order-traversal/ 这道题其实还是树的层序遍历 Binary Tree Level Order Traversal ，如果不熟悉的朋友可...

Best Time to Buy and Sell Stock III

 [Thoughts]
One dimensional dynamic planning.
Given an i, split the whole array into two parts:
[0,i] and [i+1, n], it generates two max value based on i, Max(0,i) and Max(i+1,n)
So, we can define the transformation function as:
Maxprofix = max(Max(0,i) + Max(i+1, n))  0<=i<n
------------------------------------------------------------
先从前往后找出每个i（i>0)之前（包括此位置）交易所有可能最大profit值，记录为 max_left[i].
在从后往前找出每个位置之后交易所有可能最大profit值，记录为 max_right[i].
接下来就简单了。一个for loop 解决问题。

 Solution: dp. max profit = max { l2r[0...i] + r2l[i+1...N-1] }.
0 <= i <= N-1


    int maxProfit(vector<int> &prices) {
        int N = prices.size();
        if (N <= 1) return 0;
        
        int l2r[N], r2l[N];
        l2r[0] = 0;
        r2l[N-1] = 0;
        
        int minn = prices[0];
        for (int i = 1; i < N; ++i)
        {
            minn = min(minn, prices[i]);
            l2r[i] = max(l2r[i-1], prices[i] - minn);
        }
        
        int maxx = prices[N-1];
        for (int i = N-2; i >= 0; --i)
        {
            maxx = max(maxx, prices[i]);
            r2l[i] = max(r2l[i+1], maxx - prices[i]);
        }
        
        int res = l2r[N-1];
        for (int i = 0; i < N-1; ++i)
            res = max(res, l2r[i] + r2l[i+1]);
        return res;
    }

类比： 此题可以candy的次优解法对看：http://codeganker.blogspot.com/2014/03/candy-leetcode.html 

Code Ganker: Candy -- LeetCode

Code Ganker: Candy -- LeetCode: 原题链接: http://oj.leetcode.com/problems/candy/ 这道题用到的思路和 Trapping Rain Water 是一样的，用动态规划。基本思路就是进行两次扫描，一次从左往右，一次从右往左。第一次扫描的时候维护对于每一个小孩左边所需要最少的...

Candy

最优解法：
/*
方案 ：O(n)时间，O(1)空间。
不需要记录每个孩子得到的糖果数目，只需要记录前一个孩子得到的糖果candy和
当前孩子之前rating取极大值的孩子位置maxIndex，以及该位置上孩子的糖果数maxValue。
通过这个，就可以判断需不要补糖果，以及补几颗。
*/
    int candy(vector<int> &ratings) {
        int N = ratings.size();
        if (N == 0) return 0;
        int candy = 1, res = 1;
        int maxValue = 1, maxIndex = 0;
        for (int i = 1; i < N; ++i)
        {
            if (ratings[i] >= ratings[i-1])
            {
                candy = ratings[i] == ratings[i-1] ? 1 : candy + 1;
                maxValue = candy;
                maxIndex = i;
            }
            else
            {
                if (candy == 1) {
                    if (maxValue <= i - maxIndex) {
                        res += i - maxIndex;
                        maxValue++;
                    } else {
                        res += i - maxIndex - 1;
                    }
                }
                candy = 1;
            }
            res += candy;
        }
        return res;
    }

//another one


int candy_2(vector<int> &ratings) {
    int N = ratings.size();
    if (N == 0) return 0;
    int candy[N];
    for (int i = 0; i < N; ++i)
        candy[i] = 1;
    for (int i = 1; i < N; ++i)
        if (ratings[i] > ratings[i-1])
            candy[i] = candy[i-1] + 1;
    for (int i = N-2; i >= 0; --i)
        if (ratings[i] > ratings[i+1] && candy[i] <= candy[i+1])
            candy[i] = candy[i+1] + 1;
    int res = 0;
    for (int i = 0; i < N; ++i)
        res += candy[i];
    return res;
}

另外一种次优的解法：
http://codeganker.blogspot.com/2014/03/candy-leetcode.html

Code Ganker: Container With Most Water -- LeetCode

Code Ganker: Container With Most Water -- LeetCode: 原题链接: http://oj.leetcode.com/problems/container-with-most-water/ 首先一般我们都会想到brute force的方法，思路很简单，就是对每一对pair都计算一次容积，然后去最大的那个，总共有n*(n-1)/2对pa...

Median of Two Sorted Arrays

    double findMedianSortedArrays(int A[], int m, int B[], int n) {
        int total = m + n;
        if (total & 0x1)
            return findKthSortedArrays(A, m, B, n, total / 2 + 1);
        else
            return (findKthSortedArrays(A, m, B, n, total / 2) + findKthSortedArrays(A, m, B, n, total / 2 + 1)) / 2;
    }

    double findKthSortedArrays(int A[], int m, int B[], int n, int k) {
        if(m>n)
            return findKthSortedArrays(B,n,A,m,k);
        if(m==0) return B[k-1];
        if(k==1) return min(A[0],B[0]);
        int i=min(k/2,m);
        int j=k-i;
        if(A[i-1]==B[j-1])
            return A[i-1];
        else if(A[i-1]>B[j-1])  
            return findKthSortedArrays(A,i,B+j,n-j,k-j);
        else
            return findKthSortedArrays(A+i,m-i,B,j,k-i);
    }



下面是同样的意思：http://codeganker.blogspot.com/2014/02/median-of-two-sorted-arrays-leetcode.html

这道题比较直接的想法就是用Merge Sorted Array这个题的方法把两个有序数组合并，当合并到第(m+n)/2个元素的时候返回那个数即可，而且不用把结果数组存起来。算法时间复杂度是O(m+n)，空间复杂度是O(1)。因为代码比较简单，就不写出来了，跟Merge Sorted Array比较类似，大家可以参照这个题目的解法。
接下来我们考虑有没有优化的算法。优化的思想来源于order statistics，在算法导论10.3节中提到。问题等价于求两个array的第k=(m+n)/2（假设m和n分别是两个数组的元素个数）大的数是多少。基本思路是每次通过查看两个数组的第k/2大的数(假设是A[k/2],B[k/2])，如果两个A[k/2]=B[k/2]，说明当前这个数即为两个数组剩余元素的第k大的数，如果A[k/2]>B[k/2], 那么说明B的前k/2个元素都不是我们要的第k大的数，反之则排除A的前k/2个，如此每次可以排除k/2个元素，最终k=1时即为结果。总的时间复杂度为O(logk),空间复杂度也是O(logk)，即为递归栈大小。在这个题目中因为k=(m+n)/2,所以复杂度是O(log(m+n))。比起第一种解法有明显的提高，代码如下：

public double findMedianSortedArrays(int A[], int B[]) {
    if((A.length+B.length)%2==1)
        return helper(A,B,0,A.length-1,0,B.length-1,(A.length+B.length)/2+1);
    else
        return (helper(A,B,0,A.length-1,0,B.length-1,(A.length+B.length)/2) 
               +helper(A,B,0,A.length-1,0,B.length-1,(A.length+B.length)/2+1))/2.0;
}
private int helper(int A[], int B[], int i, int i2, int j, int j2, int k)
{
    int m = i2-i+1;
    int n = j2-j+1;
    if(m>n)
        return helper(B,A,j,j2,i,i2,k);
    if(m==0)
        return B[j+k-1];
    if(k==1)
        return Math.min(A[i],B[j]);
    int posA = Math.min(k/2,m);
    int posB = k-posA;
    if(A[i+posA-1]==B[j+posB-1])
        return A[i+posA-1];
    else if(A[i+posA-1]<B[j+posB-1])
        return helper(A,B,i+posA,i2,j,j+posB-1,k-posA);
    else
        return helper(A,B,i,i+posA-1,j+posB,j2,k-posB);
}

实现中还是有些细节要注意的，比如有时候剩下的数不足k/2个，那么就得剩下的，而另一个数组则需要多取一些数。但是由于这种情况发生的时候，不是把一个数组全部读完，就是可以切除k/2个数，所以不会影响算法的复杂度。
这道题的优化算法主要是由order statistics派生而来，原型应该是求topK的算法，这个问题是非常经典的问题，一般有两种解法，一种是用quick select(快速排序的subroutine),另一种是用heap。 复杂度是差不多的，有兴趣可以搜一下，网上资料很多，topK问题在海量数据处理中也是一个非常经典的问题，所以还是要重视。