# It is Miraculours!! Beat 99.9% java SelfDefined SegmentListNode solution ,3ms,with explanation O(n) space complexity and o(n)time

• first we analyse this problem : every building likes a segment ; when the high building come it will insert in the structure and change the segment it covered like the picture below:
just[ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] :
first [2,9,10] :

2）[3,7,15]

3)[5,12,12]

...
it is just like the function f(x) = [x];
so i design a stucture which will record the left of segment right of segment and the height meanwhile record the next segment just like linkedList
when a building come in find the left in the Segment list whose the interval contains the left; then find the right ; and insert this segment in ,meanwhile you should change the node between the interval of the segment in following rules recursivly:

1. it is lower than the height, it will be blocked,make the height = height'
2. it is higher than the height it will block the segment so continue;
final detete the dumplicate node with the same height;

and we should pay attention to the situation when left = left'; right = right'; curNode.next = null we will deal with specially; it is noted in the program
in this function we just swipe the buildings arr once we will get the skyline

the code :

`````` /**
* Gaussian function y = [x]
*/

class SegNode {
int begin;
int end;
int high;
SegNode next = null;

SegNode(int begin, int end, int high) {
this.begin = begin;
this.end = end;
this.high = high;
}
}

class SegTree {
SegNode root;
SegNode cur = null;

SegTree() {
root = new SegNode(0, 0, 0);
}
/**
* insert a node in the segTree
* @param arr :arr[0] : the begin of the interval
*             arr[1]: the end of the interval
*             arr[2] : the weight of the interval
* */
void insertSegNode(int[] arr) {
if (cur == null) {
root.next = new SegNode(arr[0], arr[1], arr[2]);
cur = root.next;
} else {
SegNode str = InsertStart(cur, arr);
if (str == null) return;
cur = str;
InsertEnd(str, arr);
/*deleteDuplicate(str);*/
}
}
/**
* find the end interval that the end of the node insert in
* */
private SegNode InsertEnd(SegNode node, int[] arr) {
//right is in [begin,end)
if (arr[1] >= node.begin && arr[1] < node.end) {
if (node.high < arr[2]) {
SegNode tmp = node.next;
SegNode node1 = new SegNode(arr[1], node.end, node.high);
node1.next = tmp;
node.end = arr[1];
node.high = arr[2];
node.next = node1;
}
return node;
} else {
// the insert segment's height lower than node continue; higher make the node.high = height
node.high = node.high < arr[2] ? arr[2] : node.high;
if (node.end == arr[1]) return null;
if (node.next == null) {
if (node.high <= arr[2]) {
node.end = arr[1];
} else {
node.next = new SegNode(node.end, arr[1], arr[2]);
}
return null;
}
SegNode node1 = InsertEnd(node.next, arr);
//backtracking delete the dumplicate node :[1,2,5],[2,5,5] ->[1,5,5]
if (node1 != null && node1.high == node.high) {
node.end = node1.end;
node.next = node1.next;
}
return node1;
}
}
/**
* find the the interval that the begin of the node insert in
* */
private SegNode InsertStart(SegNode node, int[] arr) {
//when the left val int [begin,end)
if (arr[0] >= node.begin && arr[0] < node.end) {
if (arr[0] > node.begin) {
if (arr[2] > node.high) {
SegNode node1 = new SegNode(arr[0], node.end, node.high);
node.end = arr[0];
node1.next = node.next;
node.next = node1;
node = node.next;

}
}
return node;
} else {
//when the node.next == null
if (node.next == null) {
//left == end
if (node.end == arr[0]) {
if (arr[2] == node.high) {
node.end = arr[1];
} else {
node.next = new SegNode(arr[0], arr[1], arr[2]);
cur = node.next;
}
} else {
SegNode node0 = new SegNode(node.end, arr[0], 0);
SegNode node1 = new SegNode(arr[0], arr[1], arr[2]);
node.next = node0;
node0.next = node1;
cur = node1;
}

return null;
}
return InsertStart(node.next, arr);
}
}

}

public List<int[]> getSkyline(int[][] buildings) {
if (buildings.length == 0) return new ArrayList<>();
List<int[]> res = new ArrayList<>();
SegTree dic = new SegTree();
for (int[] build : buildings) {
dic.insertSegNode(build);
}
SegNode node = dic.root.next;
SegNode pre = dic.root;
while (node != null) {
if (node.high != pre.high) {
int[] a = new int[2];
a[0] = node.begin;
a[1] = node.high;
}
node = node.next;
pre = pre.next;
}
int[] a = new int[2];
a[0] = pre.end;
a[1] = 0;
return res;
}
``````

any question or improvement

• It's smart of you to keep a `next` pointer in the tree node for easier iteration.

My solution without `next` runs in 38ms.

``````public class Solution {
// segment tree
class TreeNode {
int start;
int end;
int height;
TreeNode left;
TreeNode right;

TreeNode(int _start, int _end, int _height) {
start=_start;
end=_end;
height=_height;
}

void add(TreeNode n) {
if (n.end <= start) {
if (left==null) {
left = n;
} else {
}
} else if (end <=n.start) {
if (right==null) {
right = n;
} else {
}
} else {
TreeNode l=null, r=null;
if (n.start>=start && n.end <=end && height >= n.height) return;
if (n.start > start) {
l = new TreeNode(start, n.start, height);
} else if (n.start < start) {
l = new TreeNode(n.start, start, n.height);
}

if (n.end < end) {
r = new TreeNode(n.end, end, height);
} else if (n.end > end) {
r = new TreeNode(end, n.end, n.height);
}
start = Math.max(start, n.start);
end = Math.min(end, n.end);
height = Math.max(height, n.height);
}
}
}
public List<int[]> getSkyline(int[][] buildings) {
if (buildings.length==0) return ret;
TreeNode root=new TreeNode(0,Integer.MAX_VALUE,0);

for (int[] coord: buildings) {
root.add(new TreeNode(coord[0], coord[1], coord[2]));
}

Deque<TreeNode> stack = new LinkedList<>();
stack.push(root);
Map<TreeNode, Boolean> expanded = new HashMap<>();

// inorder
while (!stack.isEmpty()) {
TreeNode n = stack.pop();
if (n==null) continue;
if (expanded.getOrDefault(n, false) || n.left==null && n.right==null) {
// revisit
// skip same height
if (ret.size()==0 || ret.get(ret.size()-1)[1] != n.height)
continue;
}

stack.push(n.right);
stack.push(n);
stack.push(n.left);

expanded.put(n, true);
}

if (buildings[0][0]!=0) ret.pop();
if (ret.get(ret.size()-1)[1]==Integer.MAX_VALUE) ret.add(new int[]{Integer.MAX_VALUE, 0});

return ret;
}
}
``````

• @derek3 I think your function is more easy to understand ~,mine is difficult to read

• Hello, I think your 3rd graph is wrong, since the height in[5, 7] is 15, when a height 12 building come in, it shouldn't lower the height in [5, 7], so I think your 3rd red point should start first from 7 corresponding in x-axis.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.