leecode-C语言实现-11. 盛最多水的容器_c语言最大容器

一、题目

二、解题思路

（1）思路一

盛最多水的容器题目，面积等于长x高，高为两个木板中较短的一个板。

例如数组为：[1,8,6,2,5,4,8,3,7]，我们定义两个变量分别指向首尾，x指向1，y指向7，x的索引位为0，y的索引位为8,1小于7，也就是说以1为高的面积最大为（8-0）x 1= 8，因为长已经是最大了，高度为1的最大值我们已经找到了，x的位置向前移动一位，此时我们需要临时变量tmpx记录一下前一个索引位0。

数组变为：[8,6,2,5,4,8,3,7]，x指向8，y指向7，x的索引位为1，y的索引位为8,8大于7，也就是说以7为高的面积最大为（8-1）x 7= 49，因为长已经是最大了，高度为7的最大值我们已经找到了，y的位置向前移动一位，此时我们需要临时变量tmpy记录一下前一个索引位8。

数组变为：[8,6,2,5,4,8,3]，x指向8，y指向3，x的索引位为1，y的索引位为7,8大于3，且3小于临时变量记录的上一个y值tmpy的高，这时我们不需要计算面积，只是对比一下y当前位置的木板长度和上一块木板tmpy的长度，因为在长度减一的情况下，高度也下降了，面积是一定减少的，所以我们可以进行计算和对比最大面积，y的位置向前移动一位，不改变tmpy，后续我们以此类推得出最大面积。

建议大家看着代码，再就着上面的文字描述结合起来看，多动手多练就一定没错的。

三、虚机测试代码

#include <stdio.h>

void main()
{
    int maxArea_v0(int* height, int heightSize);
    int maxArea_v1(int* height, int heightSize);
    int maxArea_v2(int* height, int heightSize);
    int arr[] = {2,3,4,5,18,17,6};
    int size = sizeof(arr) / sizeof(int);
    printf("result0 : %d\n",maxArea_v0(arr,size));
    printf("result1 : %d\n",maxArea_v1(arr,size));
    printf("result2 : %d\n",maxArea_v2(arr,size));
}

int maxArea_v0(int* height, int heightSize)
{
    int l,r;
    int maxarea = 0;
    int tmparea = 0;
    for(l=0,r=heightSize-1; l<r; l++)
    {
        printf("start , l : %d, r : %d, maxarea : %d, tmparea : %d\n",l,r,maxarea,tmparea);
        if(height[l] <= height[r])
        {
            tmparea = height[l] * (r - l);
            if(maxarea < tmparea)
            {
                maxarea = tmparea;
            }
            continue;
        }
        else
        {
            while(l<r)
            {
                printf("med   , l : %d, r : %d, maxarea : %d, tmparea : %d\n",l,r,maxarea,tmparea);
                if(height[l] <= height[r])
                {
                    tmparea = height[l] * (r - l);
                    if(maxarea < tmparea)
                    {
                        maxarea = tmparea;
                    }
                    break;
                }
                else if(height[l] > height[r])
                {
                    tmparea = height[r] * (r - l);
                    if(maxarea < tmparea)
                    {
                        maxarea = tmparea;
                    }
                }
                r--;                
            }
        }
        r=heightSize-1;
    }
    return maxarea;
}

int maxArea_v1(int* height, int heightSize)
{
    int l = 0;
    int r = heightSize - 1;
    int maxarea = 0;
    int tmparea = 0;
    while(l<r)
    {
        if(height[l] < height[r])
        {
            tmparea = height[l] * (r - l);
            l++;
        }
        else
        {   
            tmparea = height[r] * (r - l);
            r--;
        }
        if(maxarea < tmparea)
        {
            maxarea = tmparea;
        }
    }   
    return maxarea;
}

int maxArea_v2(int* height, int heightSize)
{
    int l = 0;
    int r = heightSize - 1;
    int maxarea = 0;
    int tmparea = 0;
    int tmpl = l;
    int tmpr = r;
    while(l<r)
    {
        if(height[l] < height[r])
        {
            if(height[l] >= height[tmpl])
            {
                tmparea = height[l] * (r - l);
                tmpl = l;
                if(maxarea < tmparea)
                {
                    maxarea = tmparea;
                }
            }
            l++;
        }
        else
        {
            if(height[r] >= height[tmpr])
            {
                tmparea = height[r] * (r - l);
                tmpr = r;
                if(maxarea < tmparea)
                {
                    maxarea = tmparea;
                }
            }   
            r--;
        }
    }
    return maxarea;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128

四、虚机代码测试截图

五、leecode提交代码

int maxArea(int* height, int heightSize)
{
    int l = 0;
    int r = heightSize - 1;
    int maxarea = 0;
    int tmparea = 0;
    int tmpl = l;
    int tmpr = r;
    while(l<r)
    {
        if(height[l] < height[r])
        {
            if(height[l] >= height[tmpl])
            {
                tmparea = height[l] * (r - l);
                tmpl = l;
                if(maxarea < tmparea)
                {
                    maxarea = tmparea;
                }
            }
            l++;
        }
        else
        {
            if(height[r] >= height[tmpr])
            {
                tmparea = height[r] * (r - l);
                tmpr = r;
                if(maxarea < tmparea)
                {
                    maxarea = tmparea;
                }
            }   
            r--;
        }
    }
    return maxarea;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

六、leecode代码提交截图