Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
[分析] 用两个指针从两端往中间扫,计算两指针当前围成的矩形面积并更新全局最大值并移动高度矮的指针。方法2 做的小优化是扫描过程中,如果当前两指针中高度较矮的指针比之前的最矮指针小,则不需要计算所围成的矩形面积,因为宽和高都比之前小的情况下矩形面积必然更小。
此题思路和Trapping Rain Water的一种思路一致。
public class Solution {
public int maxArea(int[] height) {
if (height == null || height.length == 0)
return 0;
int l = 0, r = height.length - 1;
int minBar = 0, maxArea = 0;
while (l < r) {
int currMin = Math.min(height[l], height[r]);
if (currMin == height[l]) {
if (currMin > minBar)
maxArea = Math.max(maxArea, currMin * (r - l));
l++;
} else {
if (currMin > minBar)
maxArea = Math.max(maxArea, currMin * (r - l));
r--;
}
if (currMin > minBar)
minBar = currMin;
}
return maxArea;
}
public int maxArea1(int[] height) {
if (height == null || height.length == 0)
return 0;
int l = 0, r = height.length - 1;
int minBar = 0, maxArea = 0;
while (l < r) {
minBar = Math.min(height[l], height[r]);
if (minBar == height[l]) {
maxArea = Math.max(maxArea, minBar * (r - l));
l++;
} else {
maxArea = Math.max(maxArea, minBar * (r - l));
r--;
}
}
return maxArea;
}
}
分享到:
相关推荐
[LeetCode] Container With Most WaterGiven n non-negative integers a1, a2, ..., a
/*中级思路以下我觉得分析有点问题*/ 中级思路, 这样的值 有两个性质, 不妨设 (i,a)为左边 (j,b)为右边为最大值, 1.若有坐标
leetcode-goMy solution to LeetCode problems using GolangProblems 题库Array 数组NoTitle题名DifficultyStatus11Container With Most Water盛最多水的容器MediumSolved26Remove Duplicates from Sorted Array删除...
Container With Most Water 盛最多水的容器 13 Roman to Integer 罗马数字转整数 14 Longest Common Prefix 最长公共前缀 20 Valid Parentheses 有效的括号 26 Remove Duplicates from Sorted Array 删除排序数组中...
分割数组求最大差值leetcode LeetCode 学习之路 记录自己完成LeetCode的代码和结果。 序号 中文名称 英文名称 通过率 难度 1 Two Sum 47.0% 简单 2 Add Two Numbers 36.0% 中等 3 Longest Substring Without ...
Container With Most Water LeetCode 19 Remove Nth Node From End of List LeetCode 42 Trapping Rain Water LeetCode 61 RotateList LeetCode 75 Sort Colors LeetCode 125 Valid Palindrome LeetCode 167 Two Sum...
35%2☆ ☆27%3☆ ☆24%4☆ ☆ ☆21%5☆ ☆25%6☆ ☆26%7☆24%8☆ ☆13%9Palindrome Number☆35%10Regular Expression Matching☆ ☆ ☆24%:red_heart:11Container With Most Water☆ ☆36%12Integer to R
with Ruby 13. Roman to Integer 查表,通过从前往前筛选字符串,把代表的值一个个加起来 26. Remove Duplicates from Sorted Array 难度easy的题目。根据题目要求,是不能新建数组。只能在原来的基础上做修改。基本...
Container with Most Water 14 Longest Common Prefix 15 Three Sum 16 Three Sum Closest 20 Valid Parentheses 26 Remove Duplicates from Sorted Array 48 Rotate Image 53 Maximum Subarray 55 Jump Game 56 ...
leetcode给单链表加一js实现 LeetCode By JavaScript LeetCode Solutions (All By JavaScript!...Water:双指针搜索的典型例子 12 Integer to Roman: 将阿拉伯数字转换为罗马数字 38 Count and Say:
八皇后 leetcode DSA(Data Structures and Algorithm) + Practice DSA Data Structures # 名称 结构 额外 1 数组 2 链表 3 栈 ...LeetCode ...Container With Most Water Algorithm Medium 0015 3Sum A
Container With Most Water 这里题目的分析图如下: 所以我们需要找的是ai,aj中的最小值作为高,然后找(i-j)的最大值作为长 然后得到最大的容积。 所以我们这样做 用两个point来记录现在所在的x坐标(即i值) 然后...
LeetCode刷题总结 1.Two Sum 2.Add Two Numbers 3.Longest Substring Without Repeating Characters 4.Median of Two Sorted Arrays 5.Longest Palindromic Substring (Manacher算法待完成) 6.ZigZag Conversion 7....
11. Container With Most Water 13. Roman to Integer 15. 3Sum 16. 3Sum Closest 17. Letter Combinations of a Phone Number 18. 4Sum 19. Remove Nth Node From End of List 20. Valid Parentheses 21. Merge Two...
Container With Most Water 012 Integer to Roman 013 Roman to Integer 014 Longest Common Prefix 015 3Sum 016 3Sum Closest 017 Letter Combinations of a Phone Number 018 4Sum 020 Valid Parentheses 022 ...
lru cache leetcode leetcode leetcode solutions in C++ 微信公众号:曲奇泡芙 (互联网&车联网技术) solutions ..../0003-longest-substring-without-repeating-..../0011-container-with-most-water.cpp ./0012-int
Container With Most Water 问题简述:给出一个list a,找到一组i,j使得**min(a[i],a[j])*(j-i)**最大 思路:设置首位指针h,t 从较小的一段往中间移动,同时更新答案 12. Integer to Roman - >using this radix: ...
leetcode下载 ...container with most water ** 滑动窗口 219 contains duplicate, 220 contains duplicate 当遇到int[]数组时利用下标index 的关系 栈和队 leetcode: 队列: BFS 栈:DFS // 栈和递
leetcode 跳跃 LeetCode Solved by Python easy/middle/hard:15/36/5 1. Two ...Container With Most Water 盛最多水的容器 12. Integer to Roman 整数转罗马数字 13. Roman to Integer 罗马数字转
指数姓名有效码无效的代码2个 3 4 5 6 7ReverseInteger.java 8 字符串到整数(atoi) StringToInteger.java StringToInteger(Invalid).java 11 装满水的容器ContainerWithMostWater.java 12 整数到罗马...