---
# System prepended metadata

title: 1605. Find Valid Matrix Given Row and Column Sums
tags: [C++, LeetCode]

---

# LeetCode 1605. Find Valid Matrix Given Row and Column Sums

https://leetcode.com/problems/find-valid-matrix-given-row-and-column-sums/description/

## 題目大意

只給你每個 row 的元素總和集合而成的陣列 `rowSum` 跟每個 column 的元素總和集合而成的陣列 `colSum`

它們皆為非負陣列

求一個非負矩陣可以滿足 `rowSum`, `colSum`

## 思考

非負是一個重要的提示

這代表我們可以安心使用 greedy 的策略湊一個矩陣滿足所求

```cpp!
class Solution
{
public:
    vector<vector<int>> restoreMatrix(vector<int> &rowSum, vector<int> &colSum)
    {
        const int m = rowSum.size(), n = colSum.size();
        vector<vector<int>> ans(m, vector<int>(n));

        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                ans[i][j] = min(rowSum[i], colSum[j]);
                rowSum[i] -= ans[i][j];
                colSum[j] -= ans[i][j];
            }
        }

        return ans;
    }
};
```

對於 `ans[i][j]` 每次從 `rowSum[i]` 跟 `colSum[j]` 中取最小者作為其值

之後從總和中扣出該列該行中的該元素
