/**
@algorithm description: Violent solution
@steps: Iterates through all binary combinations of array elements
@Time complexity of the algorithm: O(N^2)
@Spatial complexity of the algorithm: O(1)
**/
#include <stdio.h>
#include <stdlib.h>
/**
@function: Find the smaller of the two elements
@param[in]: a: One of the two elements of the input
@param[in]: b: The other of the input's two elements
@param[out]: NA
@return: Smaller element
@author: Cohen
@data: 2021/09/17
**/
int min(int a, int b)
{
return a < b ? a : b;
}
/**
@function: Find the two array elements that make up the largest area
@param[in]: height: Array of inputs
@param[in]: heightSize: the size of input array
@param[out]: NA
@return: ret: the max area
@author: Cohen
@data: 2021/09/17
**/
int maxArea(int* height, int heightSize)
{
int ret = 0;
int midret = 0;
for (int i = 0; i < heightSize; i++)
{
for (int j = 0; j < heightSize; j++)
{
if (i >= j)
{
continue;
}
midret = min(height[i] , height[j]) * (j - i);
if (i == 0 && j == 1)
{
ret = midret;
}
else if (ret < midret)
{
ret = midret;
printf(" i = %d, j = %d\n", i, j);
}
}
}
return ret;
}
/**
@function: A test case
@param[in]: NA
@param[out]: NA
@return: NA
@author: Cohen
@data: 2021/09/17
**/
void test()
{
int heigh[9] = { 1,8,6,2,5,4,8,3,7 };
int ret = maxArea(heigh, 9);
printf("ret = %d\n", ret);
}
int main()
{
test();
system("pause");
return 0;
}
C语言 — 双指针
/**
@algorithm description: 双指针解法
@step1: 计算pre = 0 , tail = len - 1对应的面积值
@step2: 每循环一次，淘汰掉短的柱子，因为宽度已经最大，而短的柱子固定，面积不可能再增大
#a、若height[pre] < height[tail], 则pre++
#b、若height[pre] > height[tail], 则tail--
#c、若height[pre] = height[tail], 则pre++ and tail--
@Time complexity of the algorithm: O(N)
@Spatial complexity of the algorithm: O(1)
**/
#include <stdio.h>
#include <stdlib.h>
/**
@function: Find the smaller of the two elements
@param[in]: a: One of the two elements of the input
@param[in]: b: The other of the input's two elements
@param[out]: NA
@return: Smaller element
@author: Cohen
@data: 2021/09/17
**/
int min(int a, int b)
{
return a < b ? a : b;
}
/**
@function: Find the two array elements that make up the largest area
@param[in]: height: Array of inputs
@param[in]: heightSize: the size of input array
@param[out]: NA
@return: ret: the max area
@author: Cohen
@data: 2021/09/17
**/
int maxArea_lint(int* height, int heightSize)
{
int pre = 0;
int tail = heightSize - 1;
int ret = 0;
int midret = 0;
while (pre < tail)
{
midret = min(height[pre], height[tail]) * (tail - pre);
if (pre == 0 && tail == heightSize - 1)
{
ret = midret;
}
else if (midret > ret)
{
ret = midret;
}
if (height[pre] < height[tail])
{
pre++;
}
else if(height[pre] > height[tail])
{
tail--;
}
else
{
pre++;
tail--;
}
}
return ret;
}
/**
@function: A test case
@param[in]: NA
@param[out]: NA
@return: NA
@author: Cohen
@data: 2021/09/17
**/
void test11()
{
int height[] = { 1,8,6,2,5,4,8,3,7 };
int heightSize = sizeof(height) / sizeof(height[0]);
int ret = maxArea_lint(height, heightSize);
printf("ret = %d\n", ret);
}
int main11()
{
test11();
system("pause");
return 0;
}
C++ — 双指针
/**
@algorithm description: 双指针解法
@step1: 计算pre = 0 , tail = len - 1对应的面积值
@step2: 每循环一次，淘汰掉短的柱子，因为宽度已经最大，而短的柱子固定，面积不可能再增大
#a、若height[pre] < height[tail], 则pre++
#b、若height[pre] > height[tail], 则tail--
#c、若height[pre] = height[tail], 则pre++ and tail--
@Time complexity of the algorithm: O(N)
@Spatial complexity of the algorithm: O(1)
**/
#include <iostream>
#include <vector>
using namespace std;
/**
@function: Find the two array elements that make up the largest area
@param[in]: height: Array of inputs
@param[out]: NA
@return: ret: the max area
@author: Cohen
@data: 2021/09/17
**/
int maxArea(vector<int>& height)
{
int len = height.size();
int pre = 0;
int tail = len - 1;
int midret = 0;
int ret = 0;
while (pre < tail)
{
midret = min(height[pre], height[tail]) * (tail - pre);
ret = max(midret, ret);
if (height[pre] < height[tail])
{
pre++;
}
else if (height[pre] > height[tail])
{
tail--;
}
else
{
pre++;
tail--;
}
}
return ret;
}
/**
@function: A test case
@param[in]: NA
@param[out]: NA
@return: NA
@author: Cohen
@data: 2021/09/17
**/
void test_11()
{
vector<int> height;
height.push_back(1);
height.push_back(8);
height.push_back(6);
height.push_back(2);
height.push_back(5);
height.push_back(4);
height.push_back(8);
height.push_back(3);
height.push_back(7);
int ret = maxArea(height);
printf("ret = %d\n", ret);
}
int main()
{
test_11();
system("pause");
return 0;
}
python — 双指针
#!/user/bin/env python
# -*- coding:utf-8 -*-
#@Time : 2021/9/16 23:50
#@Author : Cohen
#@File : leet11.py
"""
@algorithm description: 双指针解法
@step1: 计算pre = 0 , tail = len - 1对应的面积值
@step2: 每循环一次，淘汰掉短的柱子，因为宽度已经最大，而短的柱子固定，面积不可能再增大
#a、若height[pre] < height[tail], 则pre++
#b、若height[pre] > height[tail], 则tail--
#c、若height[pre] = height[tail], 则pre++ and tail--
@Time complexity of the algorithm: O(N)
@Spatial complexity of the algorithm: O(1)
"""
"""
/**
@function: Find the two array elements that make up the largest area
@param[in]: height: Array of inputs
@param[out]: NA
@return: ret: the max area
@author: Cohen
@data: 2021/09/17
**/
"""
def maxArea(height)->int:
pre = 0
tail = len(height) - 1
ret = 0
midret = 0
while pre < tail:
midret = min(height[pre],height[tail]) * (tail - pre)
ret = max(midret,ret)
if height[pre] < height[tail]:
pre += 1
elif height[pre] > height[tail]:
tail -= 1
else:
pre += 1
tail -= 1
return ret
"""
@function: A test case
@param[in]: NA
@param[out]: NA
@return: NA
@author: Cohen
@data: 2021/09/17
"""
def test():
height = [1,8,6,2,5,4,8,3,7]
print(maxArea(height, heightSize))
def main():
test()
if __name__ == "__main__":
main()