1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public int[] findBuildings(int[] heights) {
boolean[] buildings = new boolean[heights.length];
Arrays.fill(buildings, true);
Deque<Integer> stack = new ArrayDeque<>();
int count = buildings.length;
for (int i = 0; i < heights.length; i++) {
while (!stack.isEmpty() && heights[i] >= heights[stack.peek()]) {
buildings[stack.pop()] = false;
count -= 1;
}
stack.push(i);
}
int[] ans = new int[count];
for (int i = 0, j = 0; i < buildings.length; i++) {
if (buildings[i]) {
ans[j] = i;
j += 1;
}
}
return ans;
}
}
|
单调栈.
时间复杂度: O(n) 一个元素最多经历一次出栈和进栈. boolean数组初始化O(n), 最后誊写答案O(n), 一共就是O(n)
空间复杂度: O(n) 因为用了栈和boolean数组.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public int[] findBuildings(int[] heights) {
int max = 0;
Deque<Integer> candidates = new ArrayDeque<>();
for (int i = heights.length - 1; i >= 0; i--) {
if (heights[i] > max) {
candidates.push(i);
max = heights[i];
}
}
int[] ans = new int[candidates.size()];
for (int i = 0; i < ans.length; i++) {
ans[i] = candidates.pop();
}
return ans;
}
}
|
从右到左遍历即可. 记录遇到的最高的building.
时间复杂度: O(n)
空间复杂度: O(n) 因为需要记录candidates再把candidates誊写进array中.
