双指针_11最大积水坑.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "11. Container With Most Water\n",
    "Medium\n",
    "22.1K\n",
    "1.2K\n",
    "Companies\n",
    "You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).\n",
    "\n",
    "Find two lines that together with the x-axis form a container, such that the container contains the most water.\n",
    "\n",
    "Return the maximum amount of water a container can store.\n",
    "\n",
    "Notice that you may not slant the container.\n",
    "\n",
    " \n",
    "\n",
    "Example 1:\n",
    "\n",
    "\n",
    "Input: height = [1,8,6,2,5,4,8,3,7]\n",
    "Output: 49\n",
    "Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.\n",
    "Example 2:\n",
    "\n",
    "Input: height = [1,1]\n",
    "Output: 1\n",
    " \n",
    "\n",
    "Constraints:\n",
    "\n",
    "n == height.length\n",
    "2 <= n <= 105\n",
    "0 <= height[i] <= 104\n",
    "\n",
    "1 2 1 3\n",
    "\n",
    "1 2 0 100 101 3\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "60\n",
      "8\n",
      "49\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "# 这道题的贪心思路很简单，双指针\n",
    "# 同样高度，取决于那个最小的一边\n",
    "# 同样高度，越往两边靠越大\n",
    "# 答案要么在靠近边沿的矮值，要么在逐渐往中间靠的时候的高值\n",
    "# 贪心思路的核心是不能漏掉任何一个答案，\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def maxArea(self, height: List[int]) -> int:\n",
    "        LEN=len(height)\n",
    "        ll,lprev=0,0\n",
    "        rr,rprev=LEN-1,LEN-1\n",
    "        ans=0\n",
    "        ans=max(ans,(rr-ll)*min(height[ll],height[rr]))\n",
    "        while ll<rr:# \n",
    "            if height[ll]<height[rr]: # 让小的那一方往中间收缩 找到那个更大的中间值\n",
    "                lprev=ll\n",
    "                while ll<rr and height[lprev]>=height[ll]:\n",
    "                    ll+=1\n",
    "            elif height[ll]>=height[rr]:# 让小的那方往中间收缩，找打那个更大的中间值\n",
    "                rprev=rr\n",
    "                while ll<rr and height[rprev]>=height[rr]:\n",
    "                    rr-=1\n",
    "            ans=max(ans,(rr-ll)*min(height[ll],height[rr]))\n",
    "            lprev,rprev=ll,rr\n",
    "        return ans\n",
    "                        \n",
    "solution=Solution()\n",
    "print(solution.maxArea([1,2,0,10,101,0,0,0,0,0,0,0,1,2,3,5,3]))\n",
    "print(solution.maxArea([1,2,2,4,5,3]))\n",
    "print(solution.maxArea([1,8,6,2,5,4,8,3,7]))\n",
    "print(solution.maxArea([1,1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "base",
   "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.9.12 (main, Apr  4 2022, 05:22:27) [MSC v.1916 64 bit (AMD64)]"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "7b93ae2ddedcfb4b7ddebf80c8c7984044339b2e43f10e14b9461f3e640893f2"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}