贪心算法是指在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,
它所做出的仅是在某种意义上的局部最优解。用局部解构造全局解,即从问题的某一个初始解逐步逼近给定的
目标,以尽可能快的求得更好的解。当某个算法中的某一步不能再继续前进时,算法停止。
利用贪心算法解决问题时需要解决以下两个问题:
(1)该问题是否适合贪心策略求解。
(2)如何选择贪心标准,以得到问题的最优/较优解。
贪心算法存在如下问题:
(1)不能保证解释最佳的。因为贪心算法总是从局部出发,并没有从整体考虑。
(2)贪心算法一般用来解决求最大或最小解。
(3)贪心算法只能确定某些问题的可行性范围。 ————————————————
LeetCode 402 题:
class Solution {
public String removeKdigits(String num, int k) {
if ("0".equals(num)) return "0";
if (k == num.length()) return "0";
Deque<Character> deque = new LinkedList<>();
int n = num.length();
for (int i = 0; i < n; i++) {
// 如果栈里面的元素比当前大, 则删除栈里的元素
while (!deque.isEmpty() && k != 0 && deque.peekLast() > num.charAt(i)) {
deque.pollLast();
k--;
}
deque.offerLast(num.charAt(i));
}
// 剩下的数直接从后面开始删(即从大的数开始删)
while (k != 0) {
deque.pollLast();
k--;
}
// 合并数字
String r = "";
while (!deque.isEmpty()) {
r += deque.pollFirst();
}
// 去除前导0
while (r.charAt(0) == '0' && r.length() != 1) {
r = r.substring(1);
}
return r;
}
}