|
3 | 3 | * @tag : Array; Stack; Two Pointers |
4 | 4 | * @by : Steven Cooks |
5 | 5 | * @date: Jul 15, 2015 |
6 | | - ************************************************************************* |
| 6 | + ************************************************************************** |
7 | 7 | * Description: |
8 | 8 | * |
9 | | - * Given an unsorted integer array, find the first missing positive integer. |
10 | | - * |
11 | | - * For example, Given [1,2,0] return 3, |
12 | | - * and [3,4,-1,1] return 2. |
| 9 | + * Given n non-negative integers representing an elevation map where the |
| 10 | + * width of each bar is 1, compute how much water it is able to trap after raining. |
13 | 11 | * |
14 | | - * Your algorithm should run in O(n) time and uses constant space. |
| 12 | + * For example, |
| 13 | + * Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6. |
15 | 14 | * |
16 | 15 | ************************************************************************* |
17 | 16 | * {@link https://leetcode.com/problems/trapping-rain-water/ } |
| 17 | + * @reference {@link https://leetcode.com/discuss/41688/stack-based-solution-inspired-by-largest-histogram-problem } |
18 | 18 | */ |
19 | 19 | package_042_TrappingRainWater; |
20 | 20 |
|
| 21 | +importjava.util.Stack; |
| 22 | + |
21 | 23 | /** see test {@link _042_TrappingRainWater.SolutionStackTest } */ |
22 | 24 | publicclassSolutionStack { |
23 | 25 |
|
| 26 | +// keep a non-ascending stack: element in stack is index, and their height[index] |
| 27 | +// is non-ascending order |
| 28 | +// because we need a 'valley' to trap water, for 'valley', both left and |
| 29 | +// right bar should be higher |
24 | 30 | publicinttrap(int[]height) { |
25 | | -intleft =0; |
26 | | -intright =height.length -1; |
27 | | - |
28 | | -intleftBarrier =0; |
29 | | -intrightBarrier =0; |
30 | | -intresult =0; |
31 | | - |
32 | | -while (left <=right) { |
33 | | -if (leftBarrier <=rightBarrier) { |
34 | | -// there could be a basin between leftBarrier and rightBarrier |
35 | | -// and left side is lower one |
36 | | -if (height[left] >leftBarrier) { |
37 | | -// update left barrier |
38 | | -leftBarrier =height[left]; |
39 | | - }else { |
40 | | -// trap water (leftBarrier - height[left]) * 1 |
41 | | -result +=leftBarrier -height[left]; |
42 | | - } |
43 | | -left++; |
44 | | - }else { |
45 | | -if (height[right] >rightBarrier) { |
46 | | -// update right barrier |
47 | | -rightBarrier =height[right]; |
48 | | - }else { |
49 | | -// trap water (rightBarrier - height[right]) * 1 |
50 | | -result +=rightBarrier -height[right]; |
| 31 | +Stack<Integer>indices =newStack<>(); |
| 32 | +intres =0; |
| 33 | +for (inti =0;i <height.length;i++) { |
| 34 | +while (!indices.isEmpty() &&height[i] >height[indices.peek()]) { |
| 35 | +intlow =height[indices.pop()]; |
| 36 | +if (!indices.empty()) { |
| 37 | +intw =i -indices.peek() -1; |
| 38 | +inth =Math.min(height[i],height[indices.peek()]) -low; |
| 39 | +res +=w *h; |
51 | 40 | } |
52 | | -right--; |
53 | 41 | } |
| 42 | +indices.push(i); |
54 | 43 | } |
55 | | -returnresult; |
| 44 | +returnres; |
56 | 45 | } |
57 | 46 |
|
58 | 47 | } |