LeetCode第11题: maxArea(C语言）

上一题：LeetCode第10题: isMatch(C语言）
思路：
1、基本解法
思路：建立两层循环，分别计算数组两个元素的乘积，与记录的最大值比较

int maxArea(int* height, int heightSize) {
    int max_area = 0;
    for(int i = 0; i < heightSize; i++){
        for(int j = heightSize - 1; j >= 0 && j > i; j--){
            int min_height = 0;
            if(height[i] - height[j] > 0){
                min_height = height[j];
            }
            else{
                min_height = height[i];
            }
            if((j - i) * min_height > max_area)
                max_area = (j - i) * min_height;
        }
    }
    return max_area;
}

自然，暴力破解的方法无法在LeetCode中检查通过。
2、改进解法
思路：假设最优解的左右下标分别为 i，j ，则面积area = min(height[i], height[j]) * (j - i)，这就要求 j 和 i尽量的远，这就希望 i 离数组左边界最近， j 离数组右边界最近。最理想的情况自然是最优解 i = 0，j = heightSize - 1，当然面积还跟 min(height[i], height[j])有关，我们可以从数组左右边界开始遍历数组，并比较记录最大值。
假设输入height = [1,8,6,2,5,4,8,3,7]，heightSize = 9：
对于 i = 0，j = heightSize - 1 = 8，height[i] <height[j]的时候
min(height[i], height[j]) = height[i] = 1；则area = height[0] * （8 - 0）= 8；对于木桶左边界为 i = 0时，假设右边界还可能是比当前的最右边界 j = 8还小的下标来作为最优解存在
假设为k，则k < j，对于面来说，new_area = min(height[i], height[k]) * (k - i)，因为 k < j，则若要new_area > area，必须要求min(height[i], height[k]) > min(height[i], height[j]) ，现在用反证法证明这种情况不存在：
情况一：当height[k] > height[i]时，min(height[i], height[k]) = height[i]，new_area = height[i] * (k - i) ，由于k < j，所以new_area < area；
情况二：当height[k] < height[i]时，min(height[i], height[k]) = height[k]，new_area = height[k] * (k - i) ，由于k < j，且height[k] < height[i]，所以new_area < area；
综上，对于木桶左边界为i = 0，height[i] <height[j]时，最大桶的面积的右边界 j = heightSize - 1 = 8；
既然木桶左边界为i = 0，height[i] <height[j]的情况已经确定下来，则对于木桶的左边界，可以从 i = 1开始重新进入上述逻辑，比较height[i] 、height[j]的大小，然后用min(height[i], height[j]) 作为桶一侧的边界的高度进行计算，然后用计算面积最大值和 i = 0时的记录做比较即可。
结论：从数组两侧边界向中间靠拢，每次计算min(height[i], height[j]) ，不比回溯计算，进而减少一层循环遍历可解决，时间复杂度为N。

int maxArea(int* height, int heightSize){
    int i = 0,j = heightSize - 1;
    int area;
    int result = 0;
    while(i < j)
    {
        if(height[i] < height[j])
        {
            area=height[i] * (j - i);
            int m = i + 1;
            while(m < j && height[m] <= height[i]){
                m++;
            }
            i = m;
        }
        else
        {
            area = height[j]*(j - i);
            int n = j - 1;
            while(n > i && height[n] <= height[j]){
                n--;
            }
            j = n;
        }
        if(result < area)
            result = area;
    }
    return result;

}

本系列文章，旨在打造LeetCode题目解题方法，帮助和引导同学们开阔学习算法思路，由于个人能力和精力的局限性，也会参考其他网站的代码和思路，如有侵权，请联系本人删除。
下一题：LeetCode第12题: intToRoman(C语言）

最后编辑于：2019.06.05 16:36:28