Сложность: hard
Вы устанавливаете рекламный щит и хотите, чтобы он имел наибольшую высоту. У рекламного щита будет две стальные опоры, по одной с каждой стороны. Каждая стальная опора должна быть одинаковой высоты. Вам дается набор стержней, которые можно сварить вместе. Например, если у вас есть стержни длиной 1, 2 и 3, вы можете сварить их вместе, чтобы получилась опора длиной 6. Верните наибольшую возможную высоту вашей рекламной установки. Если вы не можете установить рекламный щит, верните 0.
Пример:
Input: rods = [1,2,3,6]
Output: 6
👨💻 Алгоритм:
1⃣Определить количество строк n и длину каждой строки m.
Создать массив delete_count длиной m, который будет отслеживать количество удаляемых столбцов.
2⃣Итеративно проверить каждую пару соседних строк для всех столбцов.
Если для данной пары строк обнаружено нарушение лексикографического порядка, отметить соответствующий столбец для удаления.
3⃣Повторять процесс до тех пор, пока массив строк не станет лексикографически отсортированным.
Вернуть количество удаленных столбцов.
😎 Решение:
class Solution {
public:
int minDeletionSize(vector<string>& strs) {
int n = strs.size();
int m = strs[0].length();
vector<bool> deleteCount(m, false);
auto isSorted = [&]() {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < m; j++) {
if (deleteCount[j]) continue;
if (strs[i][j] > strs[i + 1][j]) return false;
if (strs[i][j] < strs[i + 1][j]) break;
}
}
return true;
};
while (!isSorted()) {
for (int j = 0; j < m; j++) {
if (deleteCount[j]) continue;
for (int i = 0; i < n - 1; i++) {
if (strs[i][j] > strs[i + 1][j]) {
deleteCount[j] = true;
break;
}
}
if (deleteCount[j]) break;
}
}
return count(deleteCount.begin(), deleteCount.end(), true);
}
};Ставь 👍 и забирай 📚 Базу знаний