[Leetcode] 42. Trapping Rain Water (javascript)
1689 ワード
質問する
https://leetcode.com/problems/trapping-rain-water/
問題の説明
黒い棒がn本あれば、収容できる水量(青)が必要です.
解決策
https://leetcode.com/problems/container-with-most-water/
11番と問題解決の方法はあまり違いません.
左欄と右欄から移動させます.
左欄の最大高さ(left max)と右欄の最大高さ(right max)が0であると仮定し、左、右欄のindexが出会う前に繰り返し文を実行します.
一番左側の欄(height[left])と一番右側の欄(height[righ])の高さを比較します.
左のバーが右のバーより高い場合は、
左側のバー(height[left])の高さがleft maxより小さい場合、left maxの高さからheight[left]の高さを減算し、水を加える量.(高い場合はleft maxを更新)
そして左++;あなたに作ってあげます.
逆に、右欄(height[right])の高さがright maxより小さい場合、right maxの高さからheight[right]の高さを減算し、水を加える量.(高い場合はright maxを更新)
そして右-;あなたに作ってあげます.
コード#コード#
var trap = function(height) {
let left = 0;
let right = height.length - 1;
let answer = 0;
let left_max = 0;
let right_max = 0;
while(left < right) {
if(height[left] < height[right]) {
if(height[left] >= left_max) {
left_max = height[left];
} else {
answer += left_max - height[left];
}
left ++;
} else {
if(height[right] >= right_max) {
right_max = height[right]
} else {
answer += right_max - height[right];
}
--right;
}
}
return answer;
};
Reference
この問題について([Leetcode] 42. Trapping Rain Water (javascript)), 我々は、より多くの情報をここで見つけました https://velog.io/@yeoj1n/Leetcode-42.-Trapping-Rain-Water-javascriptテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol