LeetCode接雨水算法精解：Python实现四种方法剖析无重复字符最长子串

本文深入解析了LeetCode中“接雨水”（Trapping Rain Water）与“无重复字符的最长子串”（Longest Substring Without Repeating Characters）两道经典算法题的解题思路与Python实现。重点探讨了“接雨水”问题的四种不同解法，并附上详细的代码分析与逻辑图解。

42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

解法一：动态规划（预计算左右最大值）

核心思路是计算每个柱子上方能接的水量，其值为min(左侧最大高度, 右侧最大高度) - 当前柱子高度。首先通过两次遍历，预计算出每个位置左侧和右侧的最大高度数组。

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        if len(height) < 3:
            return 0
        res = 0
        n = len(height)
        # 1. 初始化并填充左右最大高度数组
        lmax = [0] * n
        rmax = [0] * n
        for i in range(1, n-1):
            lmax[i] = max(lmax[i-1], height[i-1])
        for j in range(n-2, 0, -1):
            rmax[j] = max(rmax[j+1], height[j+1])
        # 2. 计算每个位置的积水量
        for i in range(1, n-1):
            water = min(lmax[i], rmax[i]) - height[i]
            res += water if water > 0 else 0
        return res

解法二：双指针优化

解法一需要额外的数组空间。可以优化为双指针法，在遍历过程中动态维护左右两端的当前最大值。由于水量取决于左右最大高度中的较小值，我们可以通过比较height[left]和height[right]来决定处理哪一侧。

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        if len(height) < 3:
            return 0
        res = 0
        n = len(height)
        # 2. 双指针优化，空间复杂度O(1)
        l, r = 0, n-1
        lmax, rmax = 0, 0
        while l < r:
            if height[l] <= height[r]:
                lmax = max(lmax, height[l])
                l += 1
                res += (lmax - height[l]) if lmax - height[l] > 0 else 0
            else:
                rmax = max(rmax, height[r])
                r -= 1
                res += (rmax - height[r]) if rmax - height[r] > 0 else 0
        return res

解法三：按行计算

这是一种直观但时间复杂度较高的方法。想象水从第1层到最高层逐层填充。对于每一层，从左到右扫描，找到第一个不低于当前层高的柱子作为左边界，然后累积其后低于当前层高的“坑位”数量，直到遇到下一个不低于当前层高的柱子（右边界），将累积的水量加入结果。

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        n = len(height)
        if n < 3:
            return 0
        res = 0
        maxheight = max(height)
        for i in range(1, maxheight + 1): # 遍历每一层
            tmp = 0 # 临时存储当前层累积的水量
            flag = False # 标记是否找到了左边界
            for j in range(n): # 遍历每一列
                if height[j] >= i: # 当前柱子高度 >= 当前层高
                    flag = True # 作为（新的）左/右边界
                    res += tmp # 遇到右边界，将临时水量加入结果
                    tmp = 0 # 重置临时水量
                if flag and height[j] < i: # 在左右边界之间且高度低于层高
                    tmp += 1 # 此处可以积水一格
        return res

解法四：单调栈

单调栈非常适合处理这种找第一个更高元素的问题。栈内维护柱子索引，且其对应的高度是单调递减的。当遇到一个比栈顶高的柱子时，说明形成了一个“凹槽”，栈顶元素是凹槽底部，新的栈顶是左边界，当前元素是右边界，可以计算这一层的水量。掌握算法与数据结构中的栈应用对解决此类问题至关重要。

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        # 单调栈（递减）
        stk = []
        n = len(height)
        if n < 3:
            return 0
        res = 0
        for i in range(n):
            # 当当前高度大于栈顶高度时，说明可以形成凹槽接水
            while stk and height[stk[-1]] < height[i]:
                bottom = stk.pop() # 凹槽底部索引
                if not stk: # 栈为空，说明没有左边界，无法接水
                    break
                # 计算高度：左右边界高度的最小值 - 底部高度
                h = min(height[stk[-1]], height[i]) - height[bottom]
                # 计算宽度：右边界索引 - 左边界索引 - 1
                w = i - stk[-1] - 1
                res += h * w
            stk.append(i)
        return res

3. 无重复字符的最长子串

给定一个字符串 s，请你找出其中不含有重复字符的 最长子串 的长度。

解法：滑动窗口（哈希集合）

使用滑动窗口来维护当前无重复字符的子串。用集合（Set）来记录窗口内的字符，以实现O(1)复杂度的重复判断。使用Python进行算法实现时，合理利用其内置数据结构能让代码更简洁。

算法步骤：

1. 初始化左右指针left, right指向起始，初始化结果res和集合occ。
2. 右指针right不断向右移动，并将对应字符加入集合。
3. 若right指向的字符已在集合中（发生重复），则左指针left向右移动，并从集合中移除left指向的字符，直到重复被消除。
4. 在每次右指针移动后（即确保当前窗口无重复时），更新最大长度res。

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        occ = set() # 哈希集合，记录窗口内字符
        res = 0
        n = len(s)
        left, right = 0, 0
        while right < n:
            # 当s[right]已存在时，移动左指针缩小窗口，直到去掉该重复字符
            while s[right] in occ:
                occ.remove(s[left])
                left += 1
            # 将当前字符加入窗口
            occ.add(s[right])
            # 更新结果：当前窗口长度 = right - left + 1
            res = max(res, right - left + 1)
            right += 1 # 右指针右移
        return res