solution_python/011 Container With Most Water.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 011 Container With Most Water\n",
    "- 笔记作者：CV七少\n",
    "- 学习时间：2020.6.15\n",
    "- 编程语言：python\n",
    "- 学习任务：leetcode题解\n",
    "- 题目地址：https://leetcode-cn.com/problems/container-with-most-water/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 题目:\n",
    "\n",
    "给你 n 个非负整数 $a_1,a_2, .., a_n$，每个数代表坐标中的一个点 $(i, a_i)$ 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 $(i, a_i)$ 和 $(i, 0)$。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。  \n",
    "说明：你不能倾斜容器，且 n 的值至少为 2。\n",
    "<img src='./images/1.jpg' style = 'zoom:50%'>\n",
    "图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 示例：\n",
    "示例 1:\n",
    "```\n",
    "输入：[1,8,6,2,5,4,8,3,7]\n",
    "输出：49\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 题解"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font color=#008000>**方法一：**</font> 双指针法 [题注](https://leetcode-cn.com/problems/container-with-most-water/solution/container-with-most-water-shuang-zhi-zhen-fa-yi-do/)\n",
    "```\n",
    "执行用时 :72 ms, 在所有 Python3 提交中击败了59.70%的用户\n",
    "内存消耗 :15.2 MB, 在所有 Python3 提交中击败了6.90%的用户\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "输出为: 49\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    def maxArea(self, height):\n",
    "        \"\"\"\n",
    "        :type height: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        i, j, res = 0, len(height) - 1, 0\n",
    "        while i < j:\n",
    "            if height[i] < height[j]:\n",
    "                res = max(res, height[i] * (j - i))\n",
    "                i += 1\n",
    "            else:\n",
    "                res = max(res, height[j] * (j - i))\n",
    "                j -= 1\n",
    "        return res\n",
    "    \n",
    "\"\"\"\n",
    "For Example:    input:   height = [1,8,6,2,5,4,8,3,7]\n",
    "               output:   49\n",
    "\"\"\"\n",
    "height = [1,8,6,2,5,4,8,3,7]\n",
    "                \n",
    "solution = Solution()\n",
    "result = solution.maxArea(height)\n",
    "print('输出为:', result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 参考\n",
    "1. https://leetcode-cn.com/problems/container-with-most-water/solution/container-with-most-water-shuang-zhi-zhen-fa-yi-do/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 如果你觉得有用的话：\n",
    "- 请点点 **star** 呦\n",
    "- 关注我的 [CSDN博客](https://mp.csdn.net/console/article)\n",
    "- 关注我的 [哔哩哔哩](https://space.bilibili.com/424394389/channel/detail?cid=132513)\n",
    "- 关注公众号：CV伴读社\n",
    "<img src='./images/qrcode.jpg' style='zoom:100%'>"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}