LeetCode 11. Container With Most Water题目分析代码

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. Note: You may not slant the container and n is at least 2. Subscribe to see which companies asked this question.

题目

给定 n 个非负整数 a1, a2, ..., an, 每个数代表了坐标中的一个点 (i, ai)。画 n 条垂直线,使得 i 垂直线的两个端点分别为(i, ai)和(i, 0)。找到两条线,使得其与 x 轴共同构成一个容器,以容纳最多水。 注意事项 容器不可倾斜。 样例 给出[1,3,2], 最大的储水面积是2

分析

用两根指针一头一尾,分别计算面积,然后选取高度小的那边向中间移动,因为这样才可能存在更大的面积,更新最大的面积,最后就是结果。

Paste_Image.png

代码

public class Solution {
    /**
     * @param heights: an array of integers
     * @return: an integer
     */
    int computeArea(int left, int right,  int[] heights) {
        return (right-left)*Math.min(heights[left], heights[right]);
    }
    
    public int maxArea(int[] heights) {
        //两根指针,一头一尾计算,短的那根指针向中间移动,因为只有这种情况才存在更大的情况
        int left = 0, right = heights.length-1;
        int res = 0;
        
        while(left < right) {
            res = Math.max(res, computeArea(left,right,heights));
            if(heights[left] < heights[right]) {
                left++;
                //如果小于则不必要计算,直接跳过
                while(heights[left] <= heights[left-1] && left<right)
                    left++;
            }
            else {
                right--;
                while(heights[right] <= heights[right+1] && left <right)
                    right--;
            }
        }
        return res; 
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

UOJ#179. 线性规划(线性规划)

有 nn 个实数变量 x1,x2,…,xnx1,x2,…,xn 和 mm 条约束,其中第 ii 条约束形如 ∑nj=1aijxj≤bi∑j=1naijxj≤bi...

813
来自专栏数据结构与算法

BZOJ4766: 文艺计算姬

Description "奋战三星期,造台计算机"。小W响应号召,花了三星期造了台文艺计算姬。文艺计算姬比普通计算机有更多的艺 术细胞。普通计算机能计算一个带...

3378
来自专栏我的博客

快速排序

思想: 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排...

2955
来自专栏ACM算法日常

迷宫问题(BFS问题) - POJ 3984

本题是新加入我们的大虾Gabriel童鞋写的,他是一个刚入大学的大一新生,孺子如虎也,赞!

2842
来自专栏漫漫深度学习路

tensorflow学习笔记(二十七):leaky relu

tensorflow leaky relu 在tensorflow 0.12.0及之前,都没有内置的leaky relu函数,那么我们如何实现leaky rel...

2848
来自专栏数据结构与算法

51nod1004 n^n的末位数字

题目来源: Author Ignatius.L (Hdu 1061) 基准时间限制:1 秒 空间限制:131072 KB 分值: 5  难度:1级算法题 给出一...

3586
来自专栏数据结构与算法

洛谷P1962 斐波那契数列(矩阵快速幂)

题目背景 大家都知道,斐波那契数列是满足如下性质的一个数列: • f(1) = 1 • f(2) = 1 • f(n) = f(n-1) + f(n-2) (n...

38310
来自专栏程序员互动联盟

【编程之美】最短路径

最短路径 任意给定两个数字A和B,通过将A和6个数(7,-7,5,-5,12,-12)做加减运算,运算次数不限,每个数可以被使用多次,求从A到B最少要经过多少次...

4146
来自专栏yl 成长笔记

时间复杂度的概念以及计算

The time complexity of an algorithm quantifies the amout of time taken by an alg...

1142
来自专栏Hongten

python开发_random

和java中的random()函数一样,在python中也有类似的模块random,即随机数

1072

扫码关注云+社区

领取腾讯云代金券