当前位置：
  1. 首页
  2. 剑指offer刷题第五期
  3. 问题详情

【动态规划专题】LeetCode 42. 接雨水

本问题对应课程链接：剑指offer刷题第五期

要求：

1、请打卡你的解题代码，如果能简单说一下思路则简单说一下思路。
2、给出你代码所用的时间复杂度和空间复杂度

shuaidi
162 1

共以下 1 个回答

  • 塔底的仰望 永久会员 2023年9月15日 下午9:24

    双指针法

    class Solution {
    public int trap(int[] height) {
        int ans = 0;
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        while (left < right) {
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);
            if (height[left] <= height[right]) {
                ans += leftMax - height[left];
                left++;
            } else {
                ans += rightMax - height[right];
                right--;
            }
        }

        return ans;
    }
}
    0 赞同 0 条回复

# 回答此问题

后才能回答