议事大厅-【赛码网】..

(function (){
  function readPoints(){
    var num = read_line();
    var points = [];
    for (var i = 0; i < num; i++) {
      var point = read_line().split(/\s+/);
      points.push(point);
    }
    return points;
  }
  function test(points) {
    var result = [];
    for (var i = 0; i < points.length; i++) {
      var point = points[i];
      var isPass = true;
      for (var j = 0; j < points.length; j++) {
        var point2 = points[j];
        // console.log(point, point2, point2[0] - point[0], point2[1] - point[1]);
        if ( (point2[0] - point[0]) > 0 && (point2[1] - point[1]) > 0 ) {
          isPass = false;
          break;
        }
      }
      if (isPass) {
        result.push(point);
      }
    }
    result = result.sort(function (a, b) {
      return a[0] > b[0];
    });
    return result;
  }
  function printResult(result) {
    for (var i = 0; i < result.length; i++) {
      print(result[i][0] + ' ' + result[i][1]);
    }
  }
  // var points = [[1,2],[5,3],[4,6],[7,5],[9,0]];
  var points = readPoints();
  printResult(test(points));
})();

coder_6QWD9452

我的代码思想和你的差不多，查找右上角有没有元素存在，为什么我的数据只通过50%？需要什么优化吗？

2017-08-22 21:10

coder_W88XHF4A

这代码过不去吧。。。n2，我记得用这样的思路最多过了20%

2017-08-22 21:22

coder_IFYDu0IG

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;

public class tt {
	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		List<Point> point=new ArrayList<>();
		Stack<Point> stack=new Stack<>();
		int n=in.nextInt();
		
		for(int i=0;i<n;i++) {
			point.add(new Point(in.nextInt(), in.nextInt()));
		}
		
		//按纵坐标从小到大排序
		Collections.sort(point);
		//维护一个从栈底到栈顶递减的单调栈
		for(int i=0;i<n;i++) {
			while (!stack.isEmpty()&&stack.peek().x<point.get(i).x) {
				stack.pop();
			}
			stack.push(point.get(i));
		}
		
		while (!stack.isEmpty()) {
			Point temp=stack.pop();
			System.out.println(temp.x+" "+temp.y);
		}	
	}
}
class Point implements Comparable<Point>{
	public int x;
	public int y;
	public Point(int x,int y) {
		this.x=x;
		this.y=y;
	}
	public int compareTo(Point o) {
		return this.y-o.y;
	}
}

2017-08-22 21:27