[LeetCode] 939. Minimum Area Rectangle

[grandyang]

Given a set of points in the xy-plane, determine the minimum area of a rectangle formed from these points, with sides parallel to the x and y axes.

If there isn't any rectangle, return 0.

Example 1:

Input: [[1,1],[1,3],[3,1],[3,3],[2,2]]
Output: 4

Example 2:

Input: [[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]
Output: 2

Note:

1. 1 <= points.length <= 500
2. 0 <= points[i][0] <= 40000
3. 0 <= points[i][1] <= 40000
4. All points are distinct.

这道题给了我们一堆点的坐标，问能组成的最小的矩形面积是多少，题目中限定了矩形的边一定是平行于主轴的，不会出现旋转矩形的形状。如果知道了矩形的两个对角顶点坐标，求面积就非常的简单了，但是随便取四个点并不能保证一定是矩形，不过这四个点坐标之间是有联系的，相邻的两个顶点要么横坐标，要么纵坐标，一定有一个是相等的，这个特点先记下。策略是，先找出两个对角线的顶点，一但两个对角顶点确定了，其实这个矩形的大小也就确定了，另外的两个点其实就是分别在跟这两个点具有相同的横坐标或纵坐标的点中寻找即可，为了优化查找的时间，可以事先把所有具有相同横坐标的点的纵坐标放入到一个 HashSet 中，使用一个 HashMap，建立横坐标和所有具有该横坐标的点的纵坐标的集合之间的映射。然后开始遍历任意两个点的组合，由于这两个点必须是对角顶点，所以其横纵坐标均不能相等，若有一个相等了，则跳过该组合。否则看其中任意一个点的横坐标对应的集合中是否均包含另一个点的纵坐标，均包含的话，说明另两个顶点也是存在的，就可以计算矩形的面积了，更新结果 res，若最终 res 还是初始值，说明并没有能组成矩形，返回0即可，参见代码如下：

class Solution {
public:
    int minAreaRect(vector<vector<int>>& points) {
        int res = INT_MAX, n = points.size();
        unordered_map<int, unordered_set<int>> m;
        for (auto point : points) {
            m[point[0]].insert(point[1]);
        }
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (points[i][0] == points[j][0] || points[i][1] == points[j][1]) continue;
                if (m[points[i][0]].count(points[j][1]) && m[points[j][0]].count(points[i][1])) {
                    res = min(res, abs(points[i][0] - points[j][0]) * abs(points[i][1] - points[j][1]));
                }   
            }
        }
        return res == INT_MAX ? 0 : res;
    }
};

Github 同步地址:

#939

参考资料：

https://leetcode.com/problems/minimum-area-rectangle/

https://leetcode.com/problems/minimum-area-rectangle/discuss/192025/Java-N2-Hashmap

https://leetcode.com/problems/minimum-area-rectangle/discuss/192026/C%2B%2B-hashmap-%2B-set-intersection

LeetCode All in One 题目讲解汇总(持续更新中...)

[lld2006]

blog 里面的code应该可以优化一下， 比如没有必要每两个点都检查， 只要检查不同的x对应的共有的排过序的y就可以了

class Solution {
public:
    int minAreaRect(vector<vector<int>>& points) {
      unordered_map<int, set<int>> m;
      for(int i =0; i < points.size(); ++i) m[points[i][0]].insert(points[i][1]); 
      vector<int> vx;
      vx.reserve(m.size());
      for(auto& p:m) { vx.push_back(p.first); }
      int min_area = numeric_limits<int>::max();
      for(int idx1= 0; idx1 < vx.size(); ++idx1){
        int x1 = vx[idx1];
        auto& set1 = m[x1];
        if(set1.size()<=1) continue;
        for(int idx2=idx1+1; idx2 < vx.size(); ++idx2){
          int x2 = vx[idx2];
          int delta = abs(x2-x1);
          auto& set2 = m[x2];
          if(set2.size()<=1) continue;
          vector<int> ys;
          set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(), back_inserter(ys));
          if(ys.size()<=1) continue;
          for(int i = 0; i < ys.size()-1; ++i) min_area = min((ys[i+1]-ys[i])*delta, min_area); 
        }
      }
      return (min_area==numeric_limits<int>::max()? 0:min_area);
    }
};