## 1. 题目描述

Given n non-negative integers a1, a2, …, an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example:

Input: [1,8,6,2,5,4,8,3,7]
Output: 49

## 2. 解题

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX(X, Y) (((X) > (Y)) ? (X) : (Y))
#define MIN(X, Y) (((X) < (Y)) ? (X) : (Y))

// 两层循环
int maxArea(int* height, int heightSize) {
int maxArea = 0;
int newArea = 0;
int i, j;

for (i = 0; i < heightSize; i++) {
for (j = i + 1; j < heightSize; j++) {
newArea = (j - i) * MIN(height[i], height[j]);
maxArea = MAX(newArea, maxArea);
}
}

return maxArea;
}

int main() {
int arr[] = { 1, 8, 6, 2, 5, 4, 8, 3, 7 };
printf("%d\n", maxArea(arr, 9));

system("pause");
return 0;
}

## 3. 进阶

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX(X, Y) (((X) > (Y)) ? (X) : (Y))
#define MIN(X, Y) (((X) < (Y)) ? (X) : (Y))

int maxArea_ON(int* height, int heightSize) {
int left = 0, right = heightSize - 1;
int maxArea = 0, newArea = 0;

while (left != right) {
newArea = (right - left) * MIN(height[left], height[right]);
maxArea = MAX(newArea, maxArea);
(height[left] < height[right]) ? ++left : --right;
}

return maxArea;
}

int main() {
int arr[] = { 1, 8, 6, 2, 5, 4, 8, 3, 7 };
printf("%d\n", maxArea_ON(arr, 9));

system("pause");
return 0;
}

Last modification：September 8th, 2019 at 08:25 pm