当前位置:网站首页>C language force buckle the eleventh question to find the maximum capacity of the bucket. (two methods)
C language force buckle the eleventh question to find the maximum capacity of the bucket. (two methods)
2022-07-25 00:15:00 【Take care of two dogs and never let them go bad】
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);
}边栏推荐
- Be an artistic test / development programmer and slowly change yourself
- Modify the existing annotator name in the word document
- NXP i.mx6q development board software and hardware are all open source, and the schematic diagram of the core board is provided
- 云计算三类巨头:IaaS、PaaS、SaaS,分别是什么意思,应用场景是什么?
- [LeetCode周赛复盘] 第 83 场双周赛20220723
- 动态规划-01背包滚动数组优化
- Discussion on line segment tree
- NFT chain game system development metauniverse gamefi construction
- Principle of data proxy
- [LeetCode周赛复盘] 第 303 场周赛20220724
猜你喜欢

Grafana - influxdb visual K6 output

WP wechat export chat record backup to computer

Implement a avatar looping control
![[mindspore] [xception model] script statement is suspected to be wrong](/img/86/3174f9edadf4b815a76678551cbfa5.jpg)
[mindspore] [xception model] script statement is suspected to be wrong

Weekly summary (*66): next five years

Qt项目-安防监控系统(各个界面功能实现)
![[acwing周赛复盘] 第 61 场周赛20220723](/img/8b/df2c8d516db1e7e5f2d50bcf62b2b1.png)
[acwing周赛复盘] 第 61 场周赛20220723

Install software on kubernetes cluster using helm 3 package manager
![[mindspore] [training warning] warning when executing training code](/img/5a/978889301bdd02d6474c6e5723ad97.jpg)
[mindspore] [training warning] warning when executing training code

Principle of data proxy
随机推荐
torch.nn.SyncBatchNorm.convert_ sync_ Mindspore usage corresponding to batchnorm
Install Kaspersky 2018 under win server 2012 R2
MySQL common basic commands
Leetcode 1260. two dimensional grid migration: two solutions (k simulations / one step)
Yaml writing rules and comparison between yaml and JSON
Principle of data proxy
SQL rewriting Series 6: predicate derivation
Exception, import package and file operation
Where are MySQL version numbers 6 and 7?
QT project - security monitoring system (function realization of each interface)
QT learning - using database singleton to complete login matching + registration function
数组中只出现一次的两个数字
Why does [mindspore ascend] [custom operator] repeatedly assign values to one tensor affect another tensor?
你还在使用System.currentTimeMillis()?来看看StopWatch吧
c语言:深度刨析函数栈帧
GUI basic application
Simple operation K6
[acwing周赛复盘] 第 61 场周赛20220723
Multithreading & high concurrency (the latest in the whole network: interview questions + map + Notes) the interviewer is calm
First experience of flask