当前位置:网站首页>11. Container with the most water
11. Container with the most water
2022-07-06 03:12:00 【kkkkk7210】
Simple thinking , Clear code .
subject
link :https://leetcode-cn.com/problems/container-with-most-water
Here you are. n Nonnegative integers a1,a2,…,an, Each number represents a point in the coordinate (i, ai) . Draw in coordinates n Bar vertical line , Vertical line i The two endpoints of are (i, ai) and (i, 0) . Find two of them , Make them x A container of shafts can hold the most water .
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
Example 3:
Input :height = [4,3,2,1,4]
Output :16
Example 4:
Input :height = [1,2,1]
Output :2
Tips :
n == height.length
2 <= n <= 10^5
0 <= height[i] <= 10^4
Topic analysis
This question , Think of array elements as boards of containers , The difference between subscripts is regarded as the length of the container .
The amount of water in the container = Height of short board * The difference between subscripts
The simplest rough solution is a double loop :
- The outer loop , Subscript i Fix the board on the left height[i]
- Inner circulation moves j , Get the board on the right height[j]
- The height of the water depends on the shorter board , So take height Smaller value , Multiply by the difference between subscripts (j - i)
- Compare the obtained number with the result calculated before , Take the larger value . Finally, we get the result
class Solution {
public int maxArea(int[] height) {
int ans = 0;
for (int i = 0; i < height.length ; i++) {
for (int j = height.length - 1; j > i; j--) {
int v = Math.min(height[i],height[j]) * (j-i); // Current water capacity
ans = Math.max(ans , v); // Take a large amount of water
}
}
return ans;
}
}
Double pointer optimization
Optimize the solution just now , The idea of optimization must be to reduce a cycle .
Hot topics like this interview , There is usually a solution that comes to mind at a glance , And finally after optimization O(n) Solution method .
After all , The interviewer will not choose a question without skills .
The disadvantage of violence law is for a cycle , Move the plank in only one direction . And the double pointer can achieve a cycle , Move the plank in both directions . Move height Smaller pointer .
Let me give an example to understand the idea of double pointer , I take the example of the topic 1 To illustrate :
- height[0] It's the shortest board , The value is 1
- The law of violence above , It's from right to left , Move the template on the right . The template on the right is subscript 8, Move to the left .
- The first calculation is height[0] * (8 - 0) = 8 , It is the outer cycle for height[0] The maximum of ; Continue to move the right j, Move left to 7 ,height[0] * (7 - 0) = 7, Predictably, , It will only get smaller and smaller .
- There is no need to move the subscript of the right subscript , Instead, move the left subscript , send i Move to 1 The location of . because height[1] Than height[8] Big , take height[8] As a height , Calculation height[8] * (8 - 1) = 49.
Sum up , Just now i = 0 when , No matter how we move the right pointer , The capacity of the container obtained is less than that of the container before moving , So move the left pointer . therefore , The solution of double pointer is , Each move height Smaller subscripts .
class Solution {
public int maxArea(int[] height) {
int i = 0;
int j = height.length - 1;
int ans = 0;
while (i < j) {
int result = Math.min(height[i], height[j]) * (j - i);
ans = Math.max(ans, result);
if (height[i] < height[j]) {
i++;
} else {
j--;
}
}
return ans;
}
}
Recommend to see LeetCode The official solution to this problem
This is the end of this article.
边栏推荐
- 微服务间通信
- Differences and application scenarios between resulttype and resultmap
- Prototype design
- NR modulation 1
- Reverse repackaging of wechat applet
- Problems encountered in 2022 work IV
- Apt installation ZABBIX
- Microsoft Research, UIUC & Google research | antagonistic training actor critic based on offline training reinforcement learning
- Handwriting database client
- 【若依(ruoyi)】设置主题样式
猜你喜欢
Game theory matlab
StrError & PERROR use yyds dry inventory
Misc (eternal night), the preliminary competition of the innovation practice competition of the National College Students' information security competition
svg拖动点裁剪图片js特效
Performance analysis of user login TPS low and CPU full
电机控制反Park变换和反Clarke变换公式推导
XSS challenges bypass the protection strategy for XSS injection
Explore pointers and pointer types in depth
The next industry outlet: NFT digital collection, is it an opportunity or a foam?
NR modulation 1
随机推荐
Selenium share
Item 10: Prefer scoped enums to unscoped enums.
tcpdump: no suitable device found
Princeton University, Peking University & UIUC | offline reinforcement learning with realizability and single strategy concentration
Redo file corruption repair
Reverse repackaging of wechat applet
下一个行业风口:NFT 数字藏品,是机遇还是泡沫?
继承day01
Getting started with applet cloud development - getting user search content
Overview of OCR character recognition methods
【Kubernetes 系列】一文学会Kubernetes Service安全的暴露应用
Polymorphic day02
建模规范:命名规范
How to choose PLC and MCU?
Descriptor implements ORM model
Leetcode problem solving -- 108 Convert an ordered array into a binary search tree
[concept] Web basic concept cognition
The real machine cannot access the shooting range of the virtual machine, and the real machine cannot Ping the virtual machine
Leetcode problem solving -- 99 Restore binary search tree
StrError & PERROR use yyds dry inventory