-
Notifications
You must be signed in to change notification settings - Fork 35
/
StoneWall.java
46 lines (42 loc) · 1.16 KB
/
StoneWall.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
package com.codility.lessons.StacksQueues;
import java.util.Arrays;
import java.util.Stack;
public class StoneWall {
public int solution1(int[] H) {
int[] heights = Arrays.copyOf(H, H.length + 1);
Stack<Integer> increasingHeights = new Stack<Integer>();
int blockNum = 0;
for (int height : heights) {
while (!increasingHeights.empty() && increasingHeights.peek() >= height) {
if (increasingHeights.peek() > height) {
blockNum++;
}
increasingHeights.pop();
}
increasingHeights.push(height);
}
return blockNum;
}
public int solution2(int[] H) {
int N = H.length;
int[] stack = new int[N];
int num = 0;
stack[num++] = H[0];
int result = 1;
for (int i = 1; i < N; i++) {
// store the stonewall in ascending order and pop out the larger
// stonewall than the current stonewall
while (num > 0 && stack[num - 1] > H[i]) {
num--;
}
// if the stack is empty or the top of stack isn't equal to the
// current stonewall, then we should push the current stonewall in
// the stack and add 1 to the result.
if (num == 0 || stack[num - 1] != H[i]) {
stack[num++] = H[i];
result++;
}
}
return result;
}
}