结果应该是:
但我的测试结果是:
代码如下:
class Solution {
public int rampartDefensiveLine(int[][] rampart) {
int maxLen = 0;
int n = rampart.length;
int m = rampart[0].length;
int[][] dp = new int[n][m];
for (int j = 0; j < m; j++) {
for (int i = n - 1; i >= 0; i--) {
if (rampart[i][j] == 0) {
dp[i][j] = 0;
} else {
dp[i][j] = i == n - 1 ? 1 : dp[i + 1][j] + 1;
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int len = dp[i][j];
for (int k = j + 1; k < m && dp[i][k] > 0; k++) {
if (dp[i][k] < len) {
len = dp[i][k];
}
maxLen = Math.max(maxLen, (k - j + 1) * len);
}
}
}
return maxLen;
}
}
请问我的代码哪里需要做修改呢?或是新的思路也可以,需要代码java代码谢谢
修改后的代码如下:
class Solution {
public int rampartDefensiveLine(int[][] rampart) {
int maxLen = 0;
int n = rampart.length;
int m = rampart[0].length;
int[][] dp = new int[n][m];
for (int j = 0; j < m; j++) {
for (int i = n - 1; i >= 0; i--) {
if (rampart[i][j] == 0) {
dp[i][j] = 0;
} else {
dp[i][j] = i == n - 1 ? 1 : dp[i + 1][j] + 1;
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int len = dp[i][j];
for (int k = j + 1; k < m && dp[i][k] > 0; k++) {
if (dp[i][k] < len) {
len = dp[i][k];
}
int left = j - len + 1;
int right = k + len - 1;
if (left >= 0 && right < m) {
boolean overlap = false;
for (int p = 0; p < n; p++) {
if (p != i && dp[p][j] >= len && dp[p][k] >= len) {
overlap = true;
break;
}
}
if (!overlap) {
maxLen = Math.max(maxLen, right - left + 1);
}
}
}
}
}
return maxLen;
}
}
计算城墙膨胀后的区间时,需要同时考虑城墙向左、向右、向两个方向膨胀的情况。因此,需要计算出城墙向左、向右、向两个方向膨胀后的左右边界,然后判断是否与其他城墙重叠。如果没有重叠,则更新最大长度。