How can I compute the width of a column without converting numbers to strings?

You can calculate the length of an integer by repeatedly dividing it by 10 until the number becomes 0. For negative integers, add 1 to account for the minus sign.

What is the time complexity of solving this problem?

The time complexity is O(m * n), where m is the number of rows and n is the number of columns in the grid. Each column requires examining all rows.

Can this problem be solved using a matrix-transposing approach?

While transposing the matrix could be one approach, it’s not necessary. Directly processing columns without transposing is more efficient for this problem.

How does the early stopping technique help optimize the solution?

Early stopping helps by eliminating unnecessary checks once the maximum width for a column is found, saving time and reducing redundant work.

What are common pitfalls when calculating the width of columns?

Common pitfalls include neglecting negative integers, using inefficient methods like string conversion, and not utilizing early stopping in column processing.

#2639

Easy

auto_awesome数组·matrix

LeetCode 题解工作台

查询网格图中每一列的宽度

给你一个下标从 0 开始的 m x n 整数矩阵 grid 。矩阵中某一列的宽度是这一列数字的最大字符串长度。比方说，如果 grid = [[-10], [3], [12]] ，那么唯一一列的宽度是 3 ，因为 -10 的字符串长度为 3 。请你返回一个大小为 n 的整数数组 ans ，其中…

数组矩阵

题目描述

给你一个下标从 0 开始的 m x n 整数矩阵 grid 。矩阵中某一列的宽度是这一列数字的最大 字符串长度 。

比方说，如果 grid = [[-10], [3], [12]] ，那么唯一一列的宽度是 3 ，因为 -10 的字符串长度为 3 。

请你返回一个大小为 n 的整数数组 ans ，其中 ans[i] 是第 i 列的宽度。

一个有 len 个数位的整数 x ，如果是非负数，那么 字符串长度为 len ，否则为 len + 1 。

示例 1：

输入：grid = [[1],[22],[333]]
输出：[3]
解释：第 0 列中，333 字符串长度为 3 。

示例 2：

输入：grid = [[-15,1,3],[15,7,12],[5,6,-2]]
输出：[3,1,2]
解释：
第 0 列中，只有 -15 字符串长度为 3 。
第 1 列中，所有整数的字符串长度都是 1 。
第 2 列中，12 和 -2 的字符串长度都为 2 。

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 100
-10⁹ <= grid[r][c] <= 10⁹

lightbulb

解题思路

方法一：模拟

我们记矩阵的列数为 $n$ ，创建一个长度为 $n$ 的数组 $ans$ ，其中 $ans[i]$ 表示第 $i$ 列的宽度。初始时 $ans[i] = 0$ 。

遍历矩阵中的每一行，对于每一行中的每个元素，计算其字符串长度 $w$ ，并更新 $ans[j]$ 的值为 $\max(ans[j], w)$ 。

遍历完所有行后，数组 $ans$ 中的每个元素即为对应列的宽度。

时间复杂度 $O(m \times n)$ ，空间复杂度 $O(\log M)$ 。其中 $m$ 和 $n$ 分别为矩阵的行数和列数，而 $M$ 为矩阵中的最大元素绝对值。

1

2

3

4

class Solution:
    def findColumnWidth(self, grid: List[List[int]]) -> List[int]:
        return [max(len(str(x)) for x in col) for col in zip(*grid)]

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate demonstrates a solid understanding of matrix manipulation and can compute the length of integers without using string conversions.
question_mark
The candidate optimizes the solution by eliminating unnecessary checks in each column after the maximum width has been found.
question_mark
The candidate is familiar with efficient iteration through matrices and can articulate the time and space complexity clearly.

warning

常见陷阱

外企场景

error
Forgetting to account for negative integers when calculating their length, which might lead to off-by-one errors.
error
Inefficiently converting numbers to strings to compute their length, leading to higher time complexity.
error
Not considering early stopping once the maximum length for a column has been determined, which can waste time.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Instead of returning a single integer array, return the width of each row alongside the column widths.
arrow_right_alt
Extend the problem to handle floating-point numbers and account for decimal points when calculating the width.
arrow_right_alt
Implement a solution that works with dynamically sized grids (e.g., not necessarily rectangular).

help

常见问题

外企场景

继续练习

#2643 一最多的行 #2658 网格图中鱼的最大数目 #2617 网格图中最少访问的格子数