盛最多水的容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
1、找出所有可能情况，时间复杂度为O()，太耗时
class Solution:
def maxArea(self, height: List[int]) -> int:
max_area=0
for i in range(len(height)):
for j in range(i+1,len(height)-1):
area=(j-i)*min(height[i],heifht[j])
max_area=max(max_area,area)
return
2、双指针，时间复杂度O(n)
class Solution:
def maxArea(self, height: List[int]) -> int:
left,right=0,len(height)-1
max_area=0
while left<right:
if height[left]<=height[right]:
area=(right-left+1)*height[left]
left+=1
else:
area=(right-left+1)*height[right]
right-=1
if area>max_area:
max_area=area
return max_area
爬楼梯
假设你正在爬楼梯。需要 n阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
解题思路懵逼的时候
暴力？基本情况？
编程解决问题只能是if else,for while，recursion
找最近重复子问题
台阶1：1
台阶2：2
台阶3：f(1)+f(2)
台阶4：f(2)+f(3)
f(n)=f(n-1)+f(n-2)
这是一个斐波那契数列问题，用简单递归法时间复杂度为O()，用递推公式时间复杂度为O(n)。
class Solution:
def climbStairs(self, n: int) -> int:
if n<=2:return n
f1,f2=1,2
for i in range(3,n+1):
f1,f2=f2,f1+f2
return f2
盛最多水的容器
