Skip to content

Instantly share code, notes, and snippets.

@HuanxinHu

HuanxinHu/index.html

Created February 12, 2018 06:01
Show Gist options
  • Save HuanxinHu/6659bd2fadb8d09c1a9adb3359474180 to your computer and use it in GitHub Desktop.
Save HuanxinHu/6659bd2fadb8d09c1a9adb3359474180 to your computer and use it in GitHub Desktop.
Download ZIP
JS Bin // source http://jsbin.com/fiveqah
Raw
index.html
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width">
<title>JS Bin</title>
</head>
<body>
<script id="jsbin-javascript">
var getSkyline = function (buildings) {
var res = [];
var heights = [];
for (var i = 0; i < buildings.length; i++) {
var b = buildings[i];
heights.push([b[0], -b[2]], [b[1], b[2]]); // 上升沿用负数区分,下降沿就是本身
}
heights.sort((a, b) => a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]); // 按照x坐标以及高度排序
console.log('heights', heights);
var pq = new PriorityQueue(); // pq存高度 要用最大堆
var preMax = 0;
pq.add(0); // 0的高度是默认的
for (var i = 0; i < heights.length; i++) {
var h = heights[i];
console.log('before op: ' + 'h: [' + h + '], pq: [' + pq.getElements() + ']')
if (h[1] < 0) {
pq.add(-h[1]); // 如果是上升沿 就放入正的高度
} else {
pq.remove(h[1]); // 如果是下降沿 就remove掉, 因为我们不想要下降沿位置的高度
}
var curHeight = pq.peek();
console.log('after op: ' + pq.getElements())
console.log('curHeight: '+ curHeight + ' preMax: ' + preMax);
if (curHeight !== preMax) { // 保证一条线上只有最左边
res.push([h[0], curHeight])
preMax = curHeight;
}
console.log('res:', res);
}
return res;
};
function PriorityQueue() {
var items = [];
var QueItem = function (e, p) {
this.element = e;
this.priority = p;
}
this.add = function (e, p) {
p = p === undefined ? e : p;
var qItem = new QueItem(e, p);
if (items.length === 0) {
items.push(qItem);
} else {
var added = false;
for (var i = 0; i < items.length; i++) {
if (qItem.priority < items[i].priority) {
items.splice(i, 0, qItem);
added = true;
break;
}
}
if (!added) items.push(qItem);
}
}
this.remove = function (ele) {
for (var i = 0; i < items.length; i++) {
if (items[i].element === ele) {
items.splice(i, 1);
break;
}
}
}
this.peek = function () {
return items[items.length - 1].element;
}
this.getElements = function(){
return items.map(item => item.element);
}
}
getSkyline([ [2, 9, 10], [3, 7, 15], [5, 12, 12], [15, 20, 10], [19, 24, 8] ])
</script>
<script id="jsbin-source-javascript" type="text/javascript">var getSkyline = function (buildings) {
var res = [];
var heights = [];
for (var i = 0; i < buildings.length; i++) {
var b = buildings[i];
heights.push([b[0], -b[2]], [b[1], b[2]]); // 上升沿用负数区分,下降沿就是本身
}
heights.sort((a, b) => a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]); // 按照x坐标以及高度排序
console.log('heights', heights);
var pq = new PriorityQueue(); // pq存高度 要用最大堆
var preMax = 0;
pq.add(0); // 0的高度是默认的
for (var i = 0; i < heights.length; i++) {
var h = heights[i];
console.log('before op: ' + 'h: [' + h + '], pq: [' + pq.getElements() + ']')
if (h[1] < 0) {
pq.add(-h[1]); // 如果是上升沿 就放入正的高度
} else {
pq.remove(h[1]); // 如果是下降沿 就remove掉, 因为我们不想要下降沿位置的高度
}
var curHeight = pq.peek();
console.log('after op: ' + pq.getElements())
console.log('curHeight: '+ curHeight + ' preMax: ' + preMax);
if (curHeight !== preMax) { // 保证一条线上只有最左边
res.push([h[0], curHeight])
preMax = curHeight;
}
console.log('res:', res);
}
return res;
};
function PriorityQueue() {
var items = [];
var QueItem = function (e, p) {
this.element = e;
this.priority = p;
}
this.add = function (e, p) {
p = p === undefined ? e : p;
var qItem = new QueItem(e, p);
if (items.length === 0) {
items.push(qItem);
} else {
var added = false;
for (var i = 0; i < items.length; i++) {
if (qItem.priority < items[i].priority) {
items.splice(i, 0, qItem);
added = true;
break;
}
}
if (!added) items.push(qItem);
}
}
this.remove = function (ele) {
for (var i = 0; i < items.length; i++) {
if (items[i].element === ele) {
items.splice(i, 1);
break;
}
}
}
this.peek = function () {
return items[items.length - 1].element;
}
this.getElements = function(){
return items.map(item => item.element);
}
}
getSkyline([ [2, 9, 10], [3, 7, 15], [5, 12, 12], [15, 20, 10], [19, 24, 8] ])</script></body>
</html>
Raw
jsbin.fiveqah.js
var getSkyline = function (buildings) {
var res = [];
var heights = [];
for (var i = 0; i < buildings.length; i++) {
var b = buildings[i];
heights.push([b[0], -b[2]], [b[1], b[2]]); // 上升沿用负数区分,下降沿就是本身
}
heights.sort((a, b) => a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]); // 按照x坐标以及高度排序
console.log('heights', heights);
var pq = new PriorityQueue(); // pq存高度 要用最大堆
var preMax = 0;
pq.add(0); // 0的高度是默认的
for (var i = 0; i < heights.length; i++) {
var h = heights[i];
console.log('before op: ' + 'h: [' + h + '], pq: [' + pq.getElements() + ']')
if (h[1] < 0) {
pq.add(-h[1]); // 如果是上升沿 就放入正的高度
} else {
pq.remove(h[1]); // 如果是下降沿 就remove掉, 因为我们不想要下降沿位置的高度
}
var curHeight = pq.peek();
console.log('after op: ' + pq.getElements())
console.log('curHeight: '+ curHeight + ' preMax: ' + preMax);
if (curHeight !== preMax) { // 保证一条线上只有最左边
res.push([h[0], curHeight])
preMax = curHeight;
}
console.log('res:', res);
}
return res;
};
function PriorityQueue() {
var items = [];
var QueItem = function (e, p) {
this.element = e;
this.priority = p;
}
this.add = function (e, p) {
p = p === undefined ? e : p;
var qItem = new QueItem(e, p);
if (items.length === 0) {
items.push(qItem);
} else {
var added = false;
for (var i = 0; i < items.length; i++) {
if (qItem.priority < items[i].priority) {
items.splice(i, 0, qItem);
added = true;
break;
}
}
if (!added) items.push(qItem);
}
}
this.remove = function (ele) {
for (var i = 0; i < items.length; i++) {
if (items[i].element === ele) {
items.splice(i, 1);
break;
}
}
}
this.peek = function () {
return items[items.length - 1].element;
}
this.getElements = function(){
return items.map(item => item.element);
}
}
getSkyline([ [2, 9, 10], [3, 7, 15], [5, 12, 12], [15, 20, 10], [19, 24, 8] ])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment