LuckySeven7777的专栏

Problem:

Givennnon-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], return6.

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 Marcosfor contributing this image!C

Code:

public class Solution {public int trap(int[] A) {if (A == null || A.length == 0) {return 0;}int[] leftMost = new int[A.length];int[] rightMost = new int[A.length];leftMost[0] = A[0];rightMost[A.length – 1] = A[A.length – 1];for (int i = 1; i < A.length; i++) {leftMost[i] = Math.max(leftMost[i – 1], A[i]);}for (int i = A.length – 2; i >= 0; i–) {rightMost[i] = Math.max(rightMost[i + 1], A[i]);}int sum = 0;for (int i = 1; i < A.length – 1; i ++) {sum = sum + (Math.min(rightMost[i], leftMost[i]) – A[i]);}return sum;}}

，醒来第一眼看见的是他，然后倒头继续睡。这就是我想要的幸福。