Algorithm

[LeetCode 11] Container With Most Water [C] [Runtime : 6 MS]

顿搜

2017-06-04

0 评论

575 阅读

正在检测是否收录...

06/04

1. Description

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.

2. Example

input height[] = { 1, 1 }, heightSize = 2
output 1

3. Code

int maxArea(int* height, int heightSize) {
    int mContain = 0;
    for (int * i = height, * j = height + heightSize -1; i < j;) {
        int mMinHeight = *i < *j ? *i : *j;
        int mTmpContain = (j - i) * mMinHeight;
        mContain = mContain < mTmpContain ? mTmpContain : mContain;
        while (i < j && *i <= mMinHeight) i++;
        while (i < j && *j <= mMinHeight) j--;
    }
    return mContain;
}

#include<stdio.h>

int maxArea(int* height, int heightSize) {
    int mContain = 0;
    for (int * i = height, * j = height + heightSize -1; i < j;) {
        int mMinHeight = *i < *j ? *i : *j;
        int mTmpContain = (j - i) * mMinHeight;
        mContain = mContain < mTmpContain ? mTmpContain : mContain;
        while (i < j && *i <= mMinHeight) i++;
        while (i < j && *j <= mMinHeight) j--;
    }
    return mContain;
}

int main() {
    int height[] = { 1, 1 };
    printf("%d\n",maxArea(height, 2));
    system("pause");
    return 0;
}