leetcode分类刷题：基于数组的双指针（四、小的移动）

leetcode上有些题是真的太难了，正常读题之后完全想不到要用双指针来求解，本次博客总结的题目是双指针初始时位于数组两端，哪个元素小就移动哪个指针

11. 盛最多水的容器

1、这道题放在42. 接雨水的相似题目里，可能是因为它们都有相似的双指针解法吗？从解题代码上看，可能本题的双指针更好理解一些
2、解题思路：左右指针从两侧同时遍历，哪个指针对应的元素小就更新哪个指针，等价于对应的面积可能变大；这个思路巧妙但不是那么好想

from typing import List
'''
11. 盛最多水的容器
给定一个长度为 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:break

42. 接雨水

1、下一个更大的数的变体题目，即左右两边下一个最大的数：这道题目最关键的地方在于理解题目，每个位置接雨水的量取决于左右两边的最大值，因此按照该思路定义两个数组，分别保存左右两边的最大值，然后再次遍历序列依次累计雨水量即可
2、这道题也可以按照单调栈的解法思路：按照“大小大”规律求夹着的面积，与栈的先入后出思想一致：小于栈顶元素入栈；等于栈顶元素则替换栈顶元素；大于栈顶元素则判断“大小大”计算面积，按照行为单位求雨水量
3、这道题还可以用双指针的解法思路：左右指针从两侧同时遍历，并分别维护左右两侧的最大值标记，哪个指针对应的元素小就更新哪个，等价于哪个指针可以根据两个最大值标记计算接水量，就移动哪个指针；这个思路巧妙但更难了，不是太常规

from typing import List
'''
42. 接雨水
给定 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:  # left==right时，表示定位到了数组中的最大值处了，这里不用计算，肯定不能接水if height[left] <= height[right]:  # 情况1：height[left]刚好为lMax，必有lMax<=rMax；情况2：height[left]之前的某个数# 为lMax，那么当时left能更新的条件必然是lMax<=rMax；那么在left位置，必然有lMax<=left位置自己的右侧最大值（本来就比rMax大）# 所以，left指针可以记计算接水量result += lMax - height[left]  # 因为lMax包含了left位置，所以不用担心该计算小于0left += 1lMax = max(lMax, height[left])elif height[left] > height[right]:  # 情况1：height[right]刚好为rMax，必有lMax>rMax；情况2：height[right]之前的某个数# 为lMax，那么当时right能更新的条件必然是lMax>rMax；那么在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