Java C++題解leetcode915分割數組示例

Posted on by

題目要求

題目鏈接

思路一：兩次遍歷

題目的意思也就是左半邊數組的最大值小於等於右半邊數組的最小值，那麼就找這個分界點就好；

  • 首先從後向前遍歷，找[i,n−1]裡最小的值；
  • 然後從前向後遍歷，找[0,i]裡最大的值；
  • 然後找滿足max[i]<=min[i+1]的分割點i；
  • 可以將2、3兩步結合為一步完成，由於iii從前向後不斷增大，所以用後面（較大）的值覆蓋更新之前的值。

找到分界點的索引後，隻需+1即可得到長度。

Java

class Solution {
    public int partitionDisjoint(int[] nums) {
        int n = nums.length;
        int[] minn = new int[n + 10];
        minn[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--)
            minn[i] = Math.min(minn[i + 1], nums[i]);
        for (int i = 0, maxx = 0; i < n - 1; i++) {
            maxx = Math.max(maxx, nums[i]);
            if (maxx <= minn[i + 1])
                return i + 1;
        }
        return 1; // 用例保證不出現
    }
}
  • 時間復雜度：O(n)
  • 空間復雜度：O(n)

C++

class Solution {
public:
    int partitionDisjoint(vector<int>& nums) {
        int n = nums.size();
        int minn[n + 10];
        minn[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--)
            minn[i] = min(minn[i + 1], nums[i]);
        for (int i = 0, maxx = 0; i < n - 1; i++) {
            maxx = max(maxx, nums[i]);
            if (maxx <= minn[i + 1])
                return i + 1;
        }
        return 1; // 用例保證不出現
    }
};
  • 時間復雜度：O(n)
  • 空間復雜度：O(n)

Rust

impl Solution {
    pub fn partition_disjoint(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut minn = vec![nums[n - 1]; n + 10];
        for i in (0..(n - 1)).rev() {
            minn[i] = minn[i + 1].min(nums[i]);
        }
        let mut maxx = 0;
        for i in 0..(n - 1) {
            maxx = maxx.max(nums[i]);
            if (maxx <= minn[i + 1]) {
                return (i + 1) as i32;
            }
        }
        return 1; // 用例保證不出現
    }
}
  • 時間復雜度：O(n)
  • 空間復雜度：O(n)

思路二：一次遍歷

從前向後遍歷每個節點，依次假設每個節點為最終分界點；

  • 維護當前遍歷節點的最大值maxx，即[0,i]內；
  • 記錄假設分界點i及其對應左半邊數組最大值leftMax；

若當前值nums[i]<leftMax則重新劃定分界，將當前節點納入左區間；

找到最終結果節點索引值，將其+1即得答案。

Java

class Solution {
    public int partitionDisjoint(int[] nums) {
        int leftMax = nums[0], res = 0, maxx = nums[0];
        for (int i = 1; i < nums.length - 1; i++) {
            maxx = Math.max(maxx, nums[i]);
            if (nums[i] < leftMax) {
                leftMax = maxx;
                res = i;
            }
        }
        return res + 1;
    }
}
  • 時間復雜度：O(n)
  • 空間復雜度：O(1)

C++

class Solution {
public:
    int partitionDisjoint(vector<int>& nums) {
        int leftMax = nums[0], res = 0, maxx = nums[0];
        for (int i = 1; i < nums.size() - 1; i++) {
            maxx = max(maxx, nums[i]);
            if (nums[i] < leftMax) {
                leftMax = maxx;
                res = i;
            }
        }
        return res + 1;
    }
};
  • 時間復雜度：O(n)
  • 空間復雜度：O(1)

Rust

impl Solution {
    pub fn partition_disjoint(nums: Vec<i32>) -> i32 {
        let (mut leftMax, mut res, mut maxx) = (nums[0], 0, nums[0]);
        for i in 1..(nums.len()-1) {
            maxx = maxx.max(nums[i]);
            if nums[i] < leftMax {
                leftMax = maxx;
                res = i as i32;
            }
        }
        res + 1
    }
}
  • 時間復雜度：O(n)
  • 空間復雜度：O(1)

以上就是Java C++題解leetcode915分割數組示例的詳細內容，更多關於Java C++題解分割數組的資料請關註WalkonNet其它相關文章！

推薦閱讀：