同步操作将从 编程语言算法集/Java 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
package Others;import java.util.ArrayList;import java.util.Iterator;import java.util.Scanner;public class SkylineProblem {Building[] building;int count;public void run() {Scanner sc = new Scanner(System.in);int num = sc.nextInt();this.building = new Building[num];for (int i = 0; i < num; i++) {String input = sc.next();String[] data = input.split(",");this.add(Integer.parseInt(data[0]), Integer.parseInt(data[1]), Integer.parseInt(data[2]));}this.print(this.findSkyline(0, num - 1));sc.close();}public void add(int left, int height, int right) {building[count++] = new Building(left, height, right);}public void print(ArrayList<Skyline> skyline) {Iterator<Skyline> it = skyline.iterator();while (it.hasNext()) {Skyline temp = it.next();System.out.print(temp.coordinates + "," + temp.height);if (it.hasNext()) {System.out.print(",");}}}public ArrayList<Skyline> findSkyline(int start, int end) {if (start == end) {ArrayList<Skyline> list = new ArrayList<>();list.add(new Skyline(building[start].left, building[start].height));list.add(new Skyline(building[end].right, 0));return list;}int mid = (start + end) / 2;ArrayList<Skyline> sky1 = this.findSkyline(start, mid);ArrayList<Skyline> sky2 = this.findSkyline(mid + 1, end);return this.mergeSkyline(sky1, sky2);}public ArrayList<Skyline> mergeSkyline(ArrayList<Skyline> sky1, ArrayList<Skyline> sky2) {int currentH1 = 0, currentH2 = 0;ArrayList<Skyline> skyline = new ArrayList<>();int maxH = 0;while (!sky1.isEmpty() && !sky2.isEmpty()) {if (sky1.get(0).coordinates < sky2.get(0).coordinates) {int currentX = sky1.get(0).coordinates;currentH1 = sky1.get(0).height;if (currentH1 < currentH2) {sky1.remove(0);if (maxH != currentH2) skyline.add(new Skyline(currentX, currentH2));} else {maxH = currentH1;sky1.remove(0);skyline.add(new Skyline(currentX, currentH1));}} else {int currentX = sky2.get(0).coordinates;currentH2 = sky2.get(0).height;if (currentH2 < currentH1) {sky2.remove(0);if (maxH != currentH1) skyline.add(new Skyline(currentX, currentH1));} else {maxH = currentH2;sky2.remove(0);skyline.add(new Skyline(currentX, currentH2));}}}while (!sky1.isEmpty()) {skyline.add(sky1.get(0));sky1.remove(0);}while (!sky2.isEmpty()) {skyline.add(sky2.get(0));sky2.remove(0);}return skyline;}public class Skyline {public int coordinates;public int height;public Skyline(int coordinates, int height) {this.coordinates = coordinates;this.height = height;}}public class Building {public int left;public int height;public int right;public Building(int left, int height, int right) {this.left = left;this.height = height;this.right = right;}}public static void main(String[] args) {SkylineProblem skylineProblem = new SkylineProblem();skylineProblem.run();}}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。