做电影资源网站手机版,中核二三劳务公司招聘,园区门户网站建设,网络市场的四大特点leetcode上有些题是真的太难了#xff0c;正常读题之后完全想不到要用双指针来求解#xff0c;本次博客总结的题目是双指针初始时位于数组两端#xff0c;哪个元素小就移动哪个指针 11. 盛最多水的容器 1、这道题放在42. 接雨水的相似题目里#xff0c;可能是因为它们都有相… leetcode上有些题是真的太难了正常读题之后完全想不到要用双指针来求解本次博客总结的题目是双指针初始时位于数组两端哪个元素小就移动哪个指针 11. 盛最多水的容器 1、这道题放在42. 接雨水的相似题目里可能是因为它们都有相似的双指针解法吗从解题代码上看可能本题的双指针更好理解一些 2、解题思路左右指针从两侧同时遍历哪个指针对应的元素小就更新哪个指针等价于对应的面积可能变大这个思路巧妙但不是那么好想 from typing import List11. 盛最多水的容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明你不能倾斜容器。
示例 1:输入[1,8,6,2,5,4,8,3,7]输出49 解释图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下容器能够容纳水表示为蓝色部分的最大值为 49。
题眼
思路双指针左右指针从两侧同时遍历哪个指针对应的元素小就更新哪个指针等价于对应的面积可能变大这个思路巧妙但不是那么好想
class Solution:def maxArea(self, height: List[int]) - int:left, right 0, len(height) - 1result min(height[left], height[right]) * (right - left) # result初始值为处于数组边界情况的面积while left right:if height[left] height[right]: # 更新right才可能获得更大面积right - 1elif height[left] height[right]: # 更新left才可能获得更大面积left 1result max(result, min(height[left], height[right]) * (right - left))return resultif __name__ __main__:obj Solution()while True:try:in_line input().strip().split()height [int(n) for n in in_line[1].strip()[1: -1].split(,)]print(obj.maxArea(height))except EOFError:break42. 接雨水 1、下一个更大的数的变体题目即左右两边下一个最大的数这道题目最关键的地方在于理解题目每个位置接雨水的量取决于左右两边的最大值因此按照该思路定义两个数组分别保存左右两边的最大值然后再次遍历序列依次累计雨水量即可 2、这道题也可以按照单调栈的解法思路按照“大小大”规律求夹着的面积与栈的先入后出思想一致小于栈顶元素入栈等于栈顶元素则替换栈顶元素大于栈顶元素则判断“大小大”计算面积按照行为单位求雨水量 3、这道题还可以用双指针的解法思路左右指针从两侧同时遍历并分别维护左右两侧的最大值标记哪个指针对应的元素小就更新哪个等价于哪个指针可以根据两个最大值标记计算接水量就移动哪个指针这个思路巧妙但更难了不是太常规 from typing import List42. 接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水
示例 1:输入height [0,1,0,2,1,0,1,3,2,1,2,1]输出6解释上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图在这种情况下可以接 6 个单位的雨水蓝色部分表示雨水。
题眼
思路1、模拟每个位置接雨水的量取决于左右两边的最大值因此定义两个数组分别保存左右两边的最大值包括自己闭区间考虑这种思路是按照列为单位求
雨水量的简单直观建议掌握
思路2、单调栈按照“大小大”规律求夹着的面积与栈的先入后出思想一致小于栈顶元素入栈等于栈顶元素则替换栈顶元素大于栈顶元素则判断“大小大”计算面积
这种思路按照行为单位求雨水量的这种解释不是太好理解还不如按照括号配对的思路理解按照这种思路有点难
思路3、双指针左右指针从两侧同时遍历并分别维护左右两侧的最大值标记哪个指针对应的元素小就更新哪个等价于哪个指针可以根据两个最大值标记计算接水量
就移动哪个指针这个思路巧妙但更难了不是太常规理解起来有点吃力
class Solution:def trap(self, height: List[int]) - int:# # 思路1、模拟每个位置接雨水的量取决于左右两边的最大值因此定义两个数组分别保存左右两边的最大值包括自己闭区间考虑# lmax [0] * len(height)# maxNum 0# for i in range(len(height)):# maxNum max(maxNum, height[i])# lmax[i] maxNum# rmax [0] * len(height)# maxNum 0# for i in range(len(height) - 1, -1, -1):# maxNum max(maxNum, height[i])# rmax[i] maxNum# result 0# for i in range(len(height)):# result min(lmax[i], rmax[i]) - height[i]# return result# # 思路2、单调栈按照“大小大”规律求夹着的面积与栈的先入后出思想一致小于栈顶元素入栈等于栈顶元素则替换栈顶元素# # 大于栈顶元素则判断“大小大”计算面积# stk []# result 0# for i in range(len(height)):# if len(stk) 0:# stk.append(i)# else:# if height[i] height[stk[-1]]:# stk.append(i)# elif height[i] height[stk[-1]]: # 这一步可以注释掉合并到上一步入栈# stk.pop()# stk.append(i)# elif height[i] height[stk[-1]]:# while len(stk) 0 and height[i] height[stk[-1]]:# right height[i]# mid height[stk.pop()]# if len(stk) 0:# left height[stk[-1]]# result (min(left, right) - mid) * (i - stk[-1] - 1)# stk.append(i)# return result# 思路3、双指针左右指针从两侧同时遍历并分别维护左右两侧的最大值标记哪个指针对应的元素小就更新哪个等价于哪个指针可以根据两个最大值标# 记计算接水量就移动哪个指针left, right 0, len(height) - 1lMax, rMax height[left], height[right] # lMax标记了left位置的左侧最大值包括left本身rMax标记了right位置的右侧最大值# 包括right本身result 0while left right: # leftright时表示定位到了数组中的最大值处了这里不用计算肯定不能接水if height[left] height[right]: # 情况1height[left]刚好为lMax必有lMaxrMax情况2height[left]之前的某个数# 为lMax那么当时left能更新的条件必然是lMaxrMax那么在left位置必然有lMaxleft位置自己的右侧最大值本来就比rMax大# 所以left指针可以记计算接水量result lMax - height[left] # 因为lMax包含了left位置所以不用担心该计算小于0left 1lMax max(lMax, height[left])elif height[left] height[right]: # 情况1height[right]刚好为rMax必有lMaxrMax情况2height[right]之前的某个数# 为lMax那么当时right能更新的条件必然是lMaxrMax那么在right位置必然有right位置自己的左侧最大值本来就比lMax大rMax# 所以right指针可以记计算接水量result rMax - height[right] # 因为rMax包含了right位置所以不用担心该计算小于0right - 1rMax max(rMax, height[right])return resultif __name__ __main__:obj Solution()while True:try:in_line input().strip().split()height [int(n) for n in in_line[1].strip()[1: -1].split(,)]print(obj.trap(height))except EOFError:break
