首页 > 代码库 > [LeetCode] Trapping Rain Water

[LeetCode] Trapping Rain Water

2024-07-09 17:44:53   223人阅读

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

For example, 
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

The above elevation map 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. Thanks Marcos for contributing this image!

 

方法一：

时间复杂度 O(n)，空间复杂度 O(n)

对于每个柱子，找到其左右两边最高的柱子，该柱子能容纳的面积就是 min(leftMostHeight,rightMostHeight) - height。所以，

1. 从左往右扫描一遍，对于每个柱子，求取左边最大值；

2. 从右往左扫描一遍，对于每个柱子，求最大右值；

3. 再扫描一遍，把每个柱子的面积并累加。

code：

 1 class Solution { 2     public:  3         int trap(int A[], int n)  4         { 5             vector<int> left; 6             vector<int> right; 7             left.resize(n); 8             right.resize(n); 9 10             //printArray(A, n);11 12             left[0] == 0;13             right[n-1] == 0;14             15             // get the left‘s max 16             for(int i = 1; i< n;i++)17             {18                 left[i] = max(left[i-1], A[i-1]);19             }20             //printVector(left);21 22             // get the right‘s max 23             for(int i = n-2; i>=0;i--)24             {25                 right[i] = max(right[i+1], A[i+1]);26             }27             //printVector(right);28 29             // clac the trap water30             int sum =0;31             int height = 0;32             for(int i = 0; i< n;i++)33             {34                 height = min(left[i], right[i]);35                 if(height > A[i])36                     sum += height - A[i];37             }38             return sum;39         }40 };

方法二：

时间复杂度 O(n)，空间复杂度 O(1)

1. 扫描一遍，找到最高的柱子，这个柱子将数组分为两半；

2. 处理左边一半；

3. 处理右边一半。

 1 class Solution { 2     public: 3         int trap(int A[], int n) { 4             int max = 0;   5             for(int i = 0; i < n; i++) 6                 if (A[i] > A[max]) max = i; 7             int water = 0; 8             int left_max_height = 0; 9             // calc the left_max_height, at the same time update water10             for (int i = 0; i < max; i++)11                 if (A[i] > left_max_height) 12                     left_max_height = A[i];13                 else 14                     water += left_max_height - A[i];15             int right_max_height = 0;16             // calc the right_max_height, at the same time update water17             for (int i = n - 1; i > max; i--)18                 if (A[i] > right_max_height) 19                     right_max_height = A[i];20                 else 21                     water +=  right_max_height - A[i];22             return water;23         }   24 };

 

方法3：

// LeetCode, Trapping Rain Water
// 用一个栈辅助，小于栈顶的元素压入，大于等于栈顶就把栈里所有小于或
// 等于当前值的元素全部出栈处理掉，计算面积，最后把当前元素入栈
// 时间复杂度 O(n)，空间复杂度 O(n)
可以用std::pair 代替 struct Node结构
 
 1 struct Node 2 { 3     int val; 4     int index; 5     Node(){} 6     Node(int v, int idx):val(v), index(idx){} 7 }; 8  9 class Solution {10     public:11         int trap(int A[], int n) {12             stack<Node> s;13             int sum = 0;14             for(int i = 0; i < n; i++)15             {16                 int height = 0;17         // 将栈里比当前元素矮或等高的元素全部处理掉18                 while(!s.empty())19                 {20                     Node node = s.top();21             // 碰到了比当前元素高的，先计算面积，如{4,3，2}，再跳出while循环, 将当前元素压栈22                     if (A[i] < node.val ) // A[] = {4, 2,3}, calc sum23                     {24                         int width = i - node.index - 1;25                         sum += A[i] * width - height * width;26                         break;27                     }28                     else29                     {30             // node.val, height, a[i] 三者夹成的凹陷31                         int width = i - node.index - 1;32                         sum += node.val * width - height * width;33                         height = node.val;// update height34                 // 弹出栈顶，因为该元素处理完了，不再需要了35                         s.pop();36                     }37                 }38         // 所有元素都要入栈39                 s.push(Node(A[i], i));40             }41 42             return sum;43         }44 };

 


联系
我们