[leetcode]11. Container With Most Water

阳光穿透心脏的1/2处 2022-06-16 02:50 174阅读 0赞

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.

分析：一般的思路是时间复杂度为O（n^2）的两层循环，选出最大的：

public int maxArea(int[] height) {
    		int n = height.length;
    		int res = 0;
    		for(int i = 0; i < n-1; i++){
    			for(int j = i+1; j < n; j++){
    				int area = Math.min(height[i], height[j]) * (j - i);
    				res = (area > res) ? area : res;
    			}
    		}
    		return res;
        }

但是会超时，看到这样一个贪心的方法：

public class Solution {
        public int maxArea(int[] height) {
            int left = 0, right = height.length - 1;
        	int maxArea = 0;
        
        	while (left < right) {
        		maxArea = Math.max(maxArea, Math.min(height[left], height[right])
        				* (right - left));
        		if (height[left] < height[right])
        			left++;
        		else
        			right--;
        	}
        
        	return maxArea;
        }
    }

贪心的证明：假如A\[0\] < A\[n - 1\]，那么对于任意k(k < n - 1)，A\[0\]到A\[k\]能盛的水一定小于A\[0\]到A\[n - 1\]的盛水，所以我们只要关注A\[1\]到A\[n - 1\]的最大盛水量就好了。综上，每次内移小的一方，同时跟踪记录最大值。

发表评论取消回复

表情：

评论列表（有 0 条评论，174人围观）

还没有评论，来说两句吧...

相关阅读

相关【leetcode】 11. Container With Most Water

[https://leetcode-cn.com/problems/container-with-most-water/][https_leetcode-cn.com_prob

谁借莪１个温暖的怀抱￠/ 2023年08月17日 16:34/ 0 赞/ 95 阅读

相关 LeetCode - Medium - 11. Container With Most Water

Topic Array Two Pointers Description [https://leetcode.com/problems/contain

柔情只为你懂/ 2023年01月01日 02:51/ 0 赞/ 147 阅读

相关 11 Container With Most Water

public class No11 { public static void main(String[] args) {

我会带着你远行/ 2022年08月09日 02:15/ 0 赞/ 18 阅读

相关 Leetcode: Container With Most Water

题目： Given n non-negative integers a1, a2, …, an, where each represents a point at coor

末蓝、/ 2022年08月07日 14:53/ 0 赞/ 18 阅读

相关 Container With Most Water--LeetCode

题目： Given n non-negative integers a1, a2, ..., an, where each represents a point at c

àì夳堔傛蜴生んèń/ 2022年08月05日 13:05/ 0 赞/ 148 阅读

相关 leetcode 11. Container With Most Water

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordina

旧城等待，/ 2022年07月26日 08:41/ 0 赞/ 133 阅读

相关 [leetcode]11. Container With Most Water

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordina

阳光穿透心脏的1/2处/ 2022年06月16日 02:50/ 0 赞/ 175 阅读

相关 Leetcode——11. Container With Most Water

1. 概述 Given n non-negative integers a1, a2, ..., an, where each represents a point at

Myth丶恋晨/ 2022年06月14日 01:44/ 0 赞/ 178 阅读

相关 leetcode-11 Container With Most Water

Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate

谁借莪１个温暖的怀抱￠/ 2022年05月26日 08:36/ 0 赞/ 144 阅读

相关 LeetCode Container With Most Water

试题： Given n non-negative integers a1, a2, ..., an , where each represents a point a

╰+哭是因爲堅強的太久メ/ 2021年06月24日 16:10/ 0 赞/ 286 阅读