-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path11-maxArea.h
More file actions
77 lines (63 loc) · 1.57 KB
/
11-maxArea.h
File metadata and controls
77 lines (63 loc) · 1.57 KB
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
#pragma once
#include <iostream>
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std;
/*
给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 n 的值至少为 2。
*/
class Solution
{
public:
int maxArea(std::vector<int>&Height);
int maxArea_violence(std::vector<int>&Height);
void Test11();
};
int Solution::maxArea(std::vector<int>&Height)
{
int nSize = Height.size();
if(1>= Height.size())
return 0;
int* pStart = &Height[0];
int* pEnd = &Height[nSize - 1];
int nMaxArea = INT_MIN;
while (pStart < pEnd)
{
int nTmp = (pEnd - pStart)* min(*pEnd, *pStart);
nMaxArea = max(nMaxArea, nTmp);
if (*pEnd < *pStart)
pEnd--;
else
pStart++;
}
return nMaxArea;
}
int Solution::maxArea_violence(std::vector<int>&Height)
{
if (1 >= Height.size())
{
return 0;
}
int nMaxArea = INT_MIN;
for (int iLoop = 0;iLoop < Height.size() - 1;++iLoop)
{
int nTmp = 0;
for (int j = iLoop + 1;j < Height.size();++j)
{
nTmp = std::min(Height[j], Height[iLoop]) * (j - iLoop);
nMaxArea = std::max(nMaxArea, nTmp);
}
}
return nMaxArea;
}
void Solution::Test11()
{
int a[] = { 1,8,6,2,5,4,8,3,7 };
std::vector<int> Height(a, a + 8);
int nMaxArea = maxArea(Height);
cout << nMaxArea << endl;
nMaxArea = maxArea_violence(Height);
cout << nMaxArea << endl;
}