42. Trapping Rain Water

LeetCode hard original: C# #array #csharp #hard #leetcode #math #two-pointers

Il testo del problema è tradotto dal russo per la lingua selezionata. Il codice resta invariato.

LeetCode Static

given n неотрицательных целых чисел, представляющих карту высот, где ширина каждого столбца равна 1. Вычислите, сколько воды он может удержать после дождя.

Esempio:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]

Output: 6

C# soluzione

abbinato/originale

public class Solution {
    public int Trap(int[] height) {
        if (height.Length == 0)
            return 0;
        int ans = 0;
        int size = height.Length;
        int[] left_max = new int[size];
        int[] right_max = new int[size];
        left_max[0] = height[0];
        for (int i = 1; i < size; i++) {
            left_max[i] = Math.Max(height[i], left_max[i - 1]);
        }
        right_max[size - 1] = height[size - 1];
        for (int i = size - 2; i >= 0; i--) {
            right_max[i] = Math.Max(height[i], right_max[i + 1]);
        }
        for (int i = 1; i < size - 1; i++) {
            ans += Math.Min(left_max[i], right_max[i]) - height[i];
        }
        return ans;
    }
}

C++ soluzione

bozza automatica, rivedere prima dell'invio

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int Trap(vector<int>& height) {
        if (height.size() == 0)
            return 0;
        int ans = 0;
        int size = height.size();
        vector<int>& left_max = new int[size];
        vector<int>& right_max = new int[size];
        left_max[0] = height[0];
        for (int i = 1; i < size; i++) {
            left_max[i] = max(height[i], left_max[i - 1]);
        }
        right_max[size - 1] = height[size - 1];
        for (int i = size - 2; i >= 0; i--) {
            right_max[i] = max(height[i], right_max[i + 1]);
        }
        for (int i = 1; i < size - 1; i++) {
            ans += min(left_max[i], right_max[i]) - height[i];
        }
        return ans;
    }
}

Java soluzione

abbinato/originale

class Solution {
    public int trap(int[] height) {
        if (height.length == 0) return 0;
        int ans = 0;
        int size = height.length;
        int[] left_max = new int[size];
        int[] right_max = new int[size];
        left_max[0] = height[0];
        for (int i = 1; i < size; i++) {
            left_max[i] = Math.max(height[i], left_max[i - 1]);
        }
        right_max[size - 1] = height[size - 1];
        for (int i = size - 2; i >= 0; i--) {
            right_max[i] = Math.max(height[i], right_max[i + 1]);
        }
        for (int i = 1; i < size - 1; i++) {
            ans += Math.min(left_max[i], right_max[i]) - height[i];
        }
        return ans;
    }
}

JavaScript soluzione

abbinato/originale

var trap = function (height) {
    if (height.length == 0) return 0;
    let ans = 0;
    let size = height.length;
    let left_max = new Array(size).fill(0),
        right_max = new Array(size).fill(0);
    left_max[0] = height[0];
    for (let i = 1; i < size; i++) {
        left_max[i] = Math.max(height[i], left_max[i - 1]);
    }
    right_max[size - 1] = height[size - 1];
    for (let i = size - 2; i >= 0; i--) {
        right_max[i] = Math.max(height[i], right_max[i + 1]);
    }
    for (let i = 1; i < size - 1; i++) {
        ans += Math.min(left_max[i], right_max[i]) - height[i];
    }
    return ans;
};

Python soluzione

abbinato/originale

class Solution:
    def trap(self, height: List[int]) -> int:
        if len(height) == 0:
            return 0
        ans = 0
        size = len(height)
        left_max, right_max = [0] * size, [0] * size
        left_max[0] = height[0]
        for i in range(1, size):
            left_max[i] = max(height[i], left_max[i - 1])
        right_max[size - 1] = height[size - 1]
        for i in range(size - 2, -1, -1):
            right_max[i] = max(height[i], right_max[i + 1])
        for i in range(1, size - 1):
            ans += min(left_max[i], right_max[i]) - height[i]
        return ans

Go soluzione

abbinato/originale

func trap(height []int) int {
    if len(height) == 0 {
        return 0
    }
    ans := 0
    size := len(height)
    left_max, right_max := make([]int, size), make([]int, size)
    left_max[0] = height[0]
    for i := 1; i < size; i++ {
        if height[i] > left_max[i-1] {
            left_max[i] = height[i]
        } else {
            left_max[i] = left_max[i-1]
        }
    }
    right_max[size-1] = height[size-1]
    for i := size - 2; i >= 0; i-- {
        if height[i] > right_max[i+1] {
            right_max[i] = height[i]
        } else {
            right_max[i] = right_max[i+1]
        }
    }
    for i := 1; i < size-1; i++ {
        if left_max[i] < right_max[i] {
            ans += left_max[i] - height[i]
        } else {
            ans += right_max[i] - height[i]
        }
    }
    return ans
}

Algorithm

1️⃣

find максимальную высоту столбца с левого конца до индекса i в arrayе left_max.

2️⃣

find максимальную высоту столбца с правого конца до индекса i в arrayе right_max.

3️⃣

Итерируйте по arrayу высот height и обновляйте ans: добавьте min(left_max[i], right_max[i]) - height[i] к ans.

😎

Vacancies for this task

offerte attive with overlapping task tags are mostrati.

Tutte le offerte

Non ci sono ancora offerte attive.