You are given an integer n and a threshold integer k. Your task is to form the smallest number possible from the digits of n by deleting some digits, while maintaining the original order of the digits. The formed number must be greater than k.
Details:
You must preserve the order of the digits from n.
If the smallest number you can form is less than or equal to k, try to include additional digits from n to ensure the result is greater than k.
Function Signature:
string smallestNumberGreaterThanK(string numStr, int k);
Example 1
Input:
numStr = "7195"
k = 16Output:
"19"Explanation:
For n = 7195 and k = 16, the output should be 19.
Example 2
Input:
numStr = "7195"
k = 14Output:
"15"Explanation:
For n = 7195 and k = 14, the output should be 15.
解法
枚举所有保持原顺序的子序列长度 L，对每个 L 用单调栈贪心挑出最小子序列；若该数值大于 k 即候选。先尝试最短长度，从小到大返回首个 > k 的结果。时间复杂度 O(2ⁿ·n) 在 n ≤ 18 量级可接受；若 n 较大则改为按长度从小到大 + 单调贪心，复杂度 O(n²)。空间 O(n)。
from itertools import combinations
def smallest_number_greater_than_k(num_str: str, k: int) -> str:
n = len(num_str)
best = None
for length in range(1, n + 1):
cand_min = None
for idx in combinations(range(n), length):
s = "".join(num_str[i] for i in idx)
if s[0] == "0":
continue
val = int(s)
if val > k and (cand_min is None or val < cand_min):
cand_min = val
if cand_min is not None:
if best is None or cand_min < best:
best = cand_min
return str(best)
return ""class Solution {
String smallestNumberGreaterThanK(String numStr, int k) {
int n = numStr.length();
for (int len = 1; len <= n; len++) {
long best = Long.MAX_VALUE;
int[] idx = new int[len];
best = enumerate(numStr, k, len, 0, 0, idx, best);
if (best != Long.MAX_VALUE) return Long.toString(best);
}
return "";
}
private long enumerate(String s, int k, int len, int start, int depth, int[] idx, long best) {
if (depth == len) {
StringBuilder sb = new StringBuilder();
for (int i : idx) sb.append(s.charAt(i));
if (sb.charAt(0) == '0') return best;
long val = Long.parseLong(sb.toString());
return (val > k && val < best) ? val : best;
}
for (int i = start; i < s.length(); i++) {
idx[depth] = i;
best = enumerate(s, k, len, i + 1, depth + 1, idx, best);
}
return best;
}
}class Solution {
public:
string smallestNumberGreaterThanK(string numStr, int k) {
int n = numStr.size();
for (int len = 1; len <= n; ++len) {
long long best = LLONG_MAX;
vector<int> idx(len);
enumerate(numStr, k, len, 0, 0, idx, best);
if (best != LLONG_MAX) return to_string(best);
}
return "";
}
private:
void enumerate(const string& s, int k, int len, int start, int depth,
vector<int>& idx, long long& best) {
if (depth == len) {
string t;
for (int i : idx) t += s[i];
if (t[0] == '0') return;
long long v = stoll(t);
if (v > k && v < best) best = v;
return;
}
for (int i = start; i + (len - depth) <= (int)s.size(); ++i) {
idx[depth] = i;
enumerate(s, k, len, i + 1, depth + 1, idx, best);
}
}
};