leetcode - 42.Trapping Rain Water

2019-11-06 07:31:10

字体：大中小

来源：转载

供稿：网友

Trapping Rain Water

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.

Trapping Rain Water

Solution1:

public int trap(int[] height) { int result = 0; int left = 0; int right = height.length - 1; while (left < right) { int index; if (height[left] < height[right]) { index = left + 1; int rightHigh = height[left]; while (rightHigh > height[index] && left < right) { result += (rightHigh - height[index]); index++; } left = index; } else { index = right - 1; int rightHigh = height[right]; while (rightHigh > height[index] && left < right) { result += (rightHigh - height[index]); index--; } right = index; } } return result; }

Solution2:

public int trap(int[] height) { int result = 0; int left = 0; int right = height.length - 1; int leftHigh = 0; int rightHigh = 0; while (left < right) { leftHigh = Math.max(leftHigh, height[left]); rightHigh = Math.max(rightHigh, height[right]); if (leftHigh < rightHigh) { result += (leftHigh - height[left]); left++; } else { result += (rightHigh - height[right]); right--; } } return result; }

Solution3:

better

public int trap(int[] height) { int left = 0; int right = height.length - 1; int indexHigh = 0; int result = 0; while (left < right) { int lower = height[height[left] < height[right] ? left++ : right--]; indexHigh = Math.max(indexHigh, lower); result += indexHigh - lower; } return result; }

上一篇：萌萌哒的第二题

下一篇：PCF8591 4路AD数码管显示