[LeetCode 42]Trapping Rain Water

题目链接：trapping-rain-water

import java.util.Stack;/** * 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.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 Marcos for contributing this image! * */public class TrappingRainWater {//解法一// 315 / 315 test cases passed.// Status: Accepted// Runtime: 248 ms// Submitted: 0 minutes ago//时间复杂度O(n), 空间复杂度O(1)public int trap(int[] A) {int sum = 0;//int max = 0;for (int i = 0; i < A.length; i++) { //找到最大值if(A[i] > A[max]) {max = i;}}//计算左边int topest = 0;for (int i = 0; i < max; i++) {if(A[i] > topest) {topest = A[i];} else {sum += topest – A[i];}}//计算右边topest = 0;for (int i = A.length – 1; i > max; i–) {if(A[i] > topest) {topest = A[i];} else {sum += topest – A[i];}}return sum;}//解法二// 315 / 315 test cases passed.// Status: Accepted// Runtime: 282 ms// Submitted: 1 minute ago//时间复杂度O(n) 空间复杂度O(n)public int trap1(int[] A) {Stack<Integer> stack = new Stack<Integer>();int sum = 0;int i = 0;int max = 0;//栈中的最大值for (; i < A.length – 1; i++) {//找到最左边的最大值if (A[i] > A[i + 1]) {stack.add(A[i]);max = A[i];break;}}for (i = i + 1; i < A.length; i++) {int count = 1;while (!stack.isEmpty() && stack.peek() <= A[i]) {//如果栈顶元素小于当前元素if(A[i] >= max) {//如果当前元素大于或等于栈中的最大值while(!stack.isEmpty()) {//将栈中的元素全部出栈sum += max – stack.pop();}max = A[i];//设置当前栈的最大值} else {//如果当前元素小于栈中的最大值sum += A[i] – stack.pop();count++;//累计A[i]要进栈的次数}}while(count != 0) {stack.add(A[i]);count –;}}return sum;}public static void main(String[] args) {}}

，要温暖还是怕麻烦。