[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) { } }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。