Java&C++题解与拓展——leetcode812.最大三角形面积【么的新知识】

每日一题做题记录，参考官方和三叶的题解

目录

• 题目要求
• 思路：枚举
• • Java
  • C++
  • Rust
• 总结

题目要求

思路：枚举

• 兜兜转转考虑了一圈，结果发现是暴力模拟……

Java

class Solution {
    public double largestTriangleArea(int[][] points) {
        int n = points.length;
        double res = 0;
        for(int i = 0; i < n; i++) {
            for(int j = i + 1; j < n; j++) {
                for(int k = j + 1; k < n; k++) {
                    int cur = (points[j][0] - points[i][0]) * (points[k][1] - points[i][1]) - (points[j][1] - points[i][1]) * (points[k][0] - points[i][0]); // 叉乘计算所构成四边形的面积
                    res = Math.max(res, Math.abs(cur / 2.0));
                }
            }
        }
        return res;
    }
}

• 时间复杂度： O ( n 3 ) O(n^3) O(n3)
• 空间复杂度： O ( 1 ) O(1) O(1)

C++

class Solution {
public:
    double largestTriangleArea(vector<vector<int>>& points) {
        int n = points.size();
        double res = 0;
        for(int i = 0; i < n; i++) {
            for(int j = i + 1; j < n; j++) {
                for(int k = j + 1; k < n; k++) {
                    int cur = (points[j][0] - points[i][0]) * (points[k][1] - points[i][1]) - (points[j][1] - points[i][1]) * (points[k][0] - points[i][0]); // 叉乘计算所构成四边形的面积
                    res = max(res, abs(cur / 2.0));
                }
            }
        }
        return res;
    }
};

• 时间复杂度： O ( n 3 ) O(n^3) O(n3)
• 空间复杂度： O ( 1 ) O(1) O(1)

Rust

impl Solution {
    pub fn largest_triangle_area(points: Vec<Vec<i32>>) -> f64 {
        let n = points.len();
        let mut res : f64 = 0.0;
        for i in (0..n) {
            for j in ((i + 1)..n) {
                for k in ((j + 1)..n) {
                    let mut cur : f64 = ((points[j][0] - points[i][0]) * (points[k][1] - points[i][1]) - (points[j][1] - points[i][1]) * (points[k][0] - points[i][0])) as f64; // 叉乘计算所构成四边形的面积
                    res = res.max(cur.abs() / 2.0)
                }
            }
        }
        res
    }
}

• 时间复杂度： O ( n 3 ) O(n^3) O(n3)
• 空间复杂度： O ( 1 ) O(1) O(1)

总结

模拟总结个毛线

似乎逐渐开始懂得Rust了，such as变量定义与类型转换~生读代码也是有用的呀

欢迎指正与讨论！