LeetCode毎日1題:42.雨水を受ける
10177 ワード
JavaScriptとC++の2つのバージョンがあり、毎日更新されています.
私は複雑なデータ構造を使っていません.単純に一列で求められているので、時間の複雑さは大きいです.O(n^2)は、2列目から最後から2列目まで、現在位置する列の左右両側の最高列 をそれぞれ探し出す.の短板効果から分かるように、左右両側の最高列の中でその低いのが雨水を受けることができる限界高さ である.現在の列より高い限り、現在の列の高さを減算すると、現在の列が雨水に接することができる高さ となる.これらの雨水の高さを加算すると最終的な答え になります.
C++コード:
JSコード:
42.接雨水所与のn個の非負の整数は幅1の柱ごとの高さ図を表し、この配列の柱によって、雨が降った後にどれだけの雨水を接することができるかを計算する.
上は配列[0,1,0,2,1,0,1,3,2,1,2,1]で表される高さ図で、この場合は6単位の雨水(青い部分は雨水)をつなぐことができます.Marcosがこの図に貢献してくれたことに感謝します.
例:
入力:[0,1,0,2,1,0,1,3,2,1,2,1]出力:6
私は複雑なデータ構造を使っていません.単純に一列で求められているので、時間の複雑さは大きいです.O(n^2)
C++コード:
class Solution {
public:
int trap(vector<int>& height) {
int size=height.size(),sum=0;
//
for(int i=1;i<size-1;i++){
int max_left=0;
for(int j=0;j<i;j++) //
if(max_left<height[j])
max_left=height[j];
int max_right=0;
for(int j=i+1;j<size;j++) //
if(max_right<height[j])
max_right=height[j];
if(min(max_left,max_right)>height[i]) // ,
sum+=min(max_left,max_right)-height[i];
}
return sum;
}
};
JSコード:
/**
* @param {number[]} height
* @return {number}
*/
var trap = function(height) {
var sum=0;
//
for(var i=1;i<height.length-1;i++){
var max_left=0;
for(var j=0;j<i;j++)//
if(max_left<height[j])
max_left=height[j];
var max_right=0;
for(var j=i+1;j<height.length;j++)//
if(max_right<height[j])
max_right=height[j];
if(Math.min(max_left,max_right)>height[i])// ,
sum+=Math.min(max_left,max_right)-height[i];
}
return sum;
};
42.接雨水所与のn個の非負の整数は幅1の柱ごとの高さ図を表し、この配列の柱によって、雨が降った後にどれだけの雨水を接することができるかを計算する.
上は配列[0,1,0,2,1,0,1,3,2,1,2,1]で表される高さ図で、この場合は6単位の雨水(青い部分は雨水)をつなぐことができます.Marcosがこの図に貢献してくれたことに感謝します.
例:
入力:[0,1,0,2,1,0,1,3,2,1,2,1]出力:6