回文数

今天是小安开始Leetcode刷题的第11题，正文开始ing????

题目描述

给定 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
题目原址

示例

输入: [1,8,6,2,5,4,8,3,7]
输出: 49

方法1：暴力解法

思路

在这种情况下，我们将简单地考虑每对可能出现的线段组合并找出这些情况之下的最大面积。
注意：这个方法python会超时

代码实现

【Java实现】

public class Solution {
    public int maxArea(int[] height) {
        int maxarea = 0;
        for (int i = 0; i < height.length; i++)
            for (int j = i + 1; j < height.length; j++)
                maxarea = Math.max(maxarea, Math.min(height[i], height[j]) * (j - i));
        return maxarea;
    }
}

方法2：类快速排序

思路

像快速排序一样，i，j分别置于首尾位置，通过往中间靠拢，找寻最大容量。

代码实现

【Python实现】

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """

        ls=len(height)
        tem=min(height[1],height[0])
        v=0
        i=0#开始
        j=ls-1#结尾
        while i<j:
            w=abs(i-j)
            if height[i]<height[j]:
                h=height[i]
                i+=1# 如果i墙较低，请向前移动以寻找更高的墙。
            else:
                h=height[j]
                j-=1# 如果j墙较低，请向后移动以寻找更高的墙。
            tem=h*w
            v=max(v,tem)
        return v