游戲釣魚網站怎么做seo高級
42.?接雨水
題目:
給定?n
?個非負整數(shù)表示每個寬度為?1
?的柱子的高度圖,計算按此排列的柱子,下雨之后能接多少雨水。
示例 1:
輸入:height = [0,1,0,2,1,0,1,3,2,1,2,1] 輸出:6 解釋:上面是由數(shù)組 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度圖,在這種情況下,可以接 6 個單位的雨水(藍色部分表示雨水)。
示例 2:
輸入:height = [4,2,0,3,2,5] 輸出:9
提示:
n == height.length
1 <= n <= 2 *
0 <= height[i] <=
思路:
首先,獲取數(shù)組長度。
其次,獲取每一個點的左側和右側的最大高度。
最后,找到每一個點左側和右側最大高度較小的那個(因為只有較小的那個高度才能限制雨水容量)。將這個減去該位置的高度,即可得到該位置的雨水單位數(shù),將其累加到最終結果中。
代碼:
class Solution {
public:int trap(vector<int>& height) {int n = height.size();if (n == 0) {return 0;}vector<int> leftMax(n);leftMax[0] = height[0];for (int i = 1; i < n; ++i) {leftMax[i] = max(leftMax[i - 1], height[i]);//cout << leftMax[i] << '|';}//cout << endl;vector<int> rightMax(n);rightMax[n - 1] = height[n - 1];for (int i = n - 2; i >= 0; --i) {rightMax[i] = max(rightMax[i + 1], height[i]);//cout << rightMax[i] << '|';}//cout << endl;int ans = 0;for (int i = 0; i < n; ++i) {ans += min(leftMax[i], rightMax[i]) - height[i];//cout << min(leftMax[i], rightMax[i]) - height[i] << '|';}return ans;}
};
?