[每日一题] 2639.查询网格图中每一列的宽度

博主： Richard
发布时间：2024 年 04 月 27 日
93 次浏览
暂无评论
1654字数
分类： LeetCode

> https://leetcode.cn/problems/find-the-width-of-columns-of-a-grid/description/?envType=daily-question&envId=2024-04-07

简单题，遍历 $grid$ 中的每一列求出数字视为字符串时长度的最大值。长度最大值只可能是最大的数或最小的数，因此找出这两个数转换比较一下即可。

代码写得稍微有点复杂：

```c++
class Solution {
public:
    long long binpow(long long a, long long b) {
        if (b == 0) return 1;
        long long res = binpow(a, b / 2);
        if (b % 2)
            return res * res * a;
        else
            return res * res;
    }

std::vector<int> findColumnWidth(std::vector<std::vector<int>>& grid) {
        auto getMaxWidth = [&] (const int &j, const int &m) {
            int minValue = INT_MAX, maxValue = INT_MIN;
            for (int i = 0; i < m; ++i) {
                if (grid[i][j] < minValue)
                    minValue = grid[i][j];
                if (grid[i][j] > maxValue)
                    maxValue = grid[i][j];
            }

if (minValue == maxValue && maxValue == 0)
                return 1;

int maxWidth = minValue < 0;
            while (minValue != 0) {
                maxWidth += 1;
                minValue /= 10;
            }

maxValue /= binpow(10, maxValue < 0 ? maxWidth - 1 : maxWidth);
            while (maxValue != 0) {
                maxWidth += 1;
                maxValue /= 10;
            }

return maxWidth;
        };

int m = grid.size(), n = grid[0].size();
        std::vector<int> res(n);
        for (int j = 0; j < n; ++j)
            res[j] = getMaxWidth(j, m);
        return res;
    }
};
```

- 时间复杂度： $O(mn)$ 。其中 $m$ 是数组 $grid$ 的行数， $n$ 是数组 $grid$ 的列数。
- 空间复杂度： $O(1)$ 。

最后修改：2024 年 05 月 06 日