Leetcode-42. Trapping Rain Water [C++][Java]

目录

一、题目描述

二、解题思路

【C++】

【Java】

Leetcode-42. Trapping Rain Waterhttps://leetcode.com/problems/trapping-rain-water/description/

一、题目描述

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9

Constraints:

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

二、解题思路

【C++】

class Solution {
public:
    int trap(vector<int>& height) {
        if (height.size() == 0) {
            return 0;
        }
        int left = 0, right = height.size() - 1;
        int leftMax = height[left], rightMax = height[right], res = 0;
        while (left < right) {
            if (height[left] < height[right]) {
                res += leftMax - height[left++];
                leftMax = max(leftMax, height[left]);
            } else {
                res += rightMax - height[right--];
                rightMax = max(rightMax, height[right]);
            }
        }
        return res;
    }
};

【Java】

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