C language force buckle the eleventh question to find the maximum capacity of the bucket. (two methods)

Given a length of n Array of integers for height . Yes n Vertical line , The first i The two ends of the line are (i, 0) and (i, height[i]) .

Find two of them , Make them x A container of shafts can hold the most water .

Return the maximum amount of water that the container can store .

explain ： You can't tilt the container .

Example 1：

Input ：[1, 8, 6, 2, 5, 4, 8, 3, 7]
Output ：49
explain ： The vertical line in the figure represents the input array [1, 8, 6, 2, 5, 4, 8, 3, 7]. In this case , The container can hold water （ In blue ） The maximum value of is 49.

Example 2：

Input ：height = [1, 1]
Output ：1

Tips ：

n == height.length
2 <= n <= 105
0 <= height[i] <= 104

source ： Power button （LeetCode）
link ：https ://leetcode.cn/problems/container-with-most-water
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>


// Violence law , Probably the idea of bubble sorting 
// How much is this problem   This method is too complex to 
int test1(int* height, int heightSize) 
{
	int sum = 0;
	int left = 0;
	int right = 1;
	for (left = 0; left < heightSize - 1 ;left++)
	{
		for (right = left + 1; right < heightSize; right++)
		{
			if ((height[left] * (right - left) > sum) && (height[right] * (right - left) > sum))
			{
				if (height[left] > height[right])
					sum = height[right] * (right - left);
				else
					sum = height[left] * (right - left);
			}
		}
	}
	return sum;
}


// In each state , Whether the long board or the short board narrows one grid to the middle , Will cause the sink   Bottom edge width  −1-1−1​  shorter ：

// If inward   Move the short board  , The short board of the sink  min(h[i], h[j])min(h[i], h[j])min(h[i], h[j])  May be bigger , So the area of the next tank   May increase  .
// If inward   Move the long board  , The short board of the sink  min(h[i], h[j])min(h[i], h[j])min(h[i], h[j])​  Constant or smaller , So the area of the next tank   It must be smaller  .
//
// therefore , Initialize the double pointer to separate the left and right ends of the sink , Move the short board inward one grid in each cycle , And update the maximum area , Until the two pointers meet and jump out ; You can get the maximum area .
// Algorithm flow ：
//
// initialization ：  Double pointer  iii, jjj  Separate the left and right ends of the sink ;
// Cycle narrowing ：  Until the double pointers jump out when they meet ;
// Update area max  sum ;
// Select the short board in the two board heights , Narrow it in the middle ;
// Return value ：  Returns the maximum area  sum that will do 
// The time complexity is zero O（n）

int test2(int* height, int heightSize)
{
	int sum = 0;
	int left = 0;
	int right = heightSize-1;
	while (left <= right)
	{
		if (height[left] < height[right])
		{
			if (sum < height[left] * (right - left))
				sum = height[left] * (right - left);
			left++;
		}
		else
		{
			if (sum < height[right] * (right - left))
				sum = height[right] * (right - left);
			right--;
		}
	}
	return sum;
}



int main()
{
	int height[100] = { 1, 8, 6, 2, 5, 4, 8, 3, 7 };
	/*printf("%d", sizeof(height) / sizeof(int));*/
	int heightSize = 9;
	//int sum = test1(height, heightSize);
	int sum = test2(height, heightSize);
	printf("%d", sum);
}