給定一個以字串表示的非負整數 num，移除這個數中的 k 位數字，使得剩下的數字最小，其中
解題思路
首先我們要了解一個關于數學的前置知識，對于兩個相同長度的數字序列，最左邊不同的數字決定了這兩個數字的大小，例如，對于 A = 1axxxA = 1axxx，B = 1bxxxB = 1bxxx，如果 a > b，則 A > B
基于此，我們可以知道，若要使得剩下的數字最小，需要保證靠前的數字盡可能小
如果使用暴力法，那思路就是：
- 從左到右遍歷
- 對于每一個遍歷到的元素，前一個元素比當前元素大，則丟棄前一個元素，否則保留前一個元素
需要注意的是，如果給定的數字是一個單調遞增的數字，那么我們的演算法會永遠選擇不丟棄，這個題目中要求的，我們要永遠確保丟棄 k 個數字，因此思路還應該稍加修改：
- 每次丟棄一次，k 減去 1，當 k 減到 0 ，我們可以提前終止遍歷
- 而當遍歷完成，如果 k 仍然大于 0，不妨假設最侄訓剩下 x 個需要丟棄，那么我們需要選擇洗掉末尾 x 個元素
然而暴力的實作復雜度最差會達到 O(nk)（考慮整個數字序列是單調不降的），因此我們需要加速這個程序
可以用一個堆疊維護當前的答案序列，堆疊中的元素代表截止到當前位置，洗掉不超過 k 次個數字時，所能得到的最小整數，根據之前的討論：在使用 k 個洗掉次數之前，堆疊中的序列從堆疊底到堆疊頂單調不降，因此，對于每個數字，如果該數字小于堆疊頂元素，我們就不斷地彈出堆疊頂元素，直到
- 堆疊為空
- 新的堆疊頂元素不大于當前數字
- 已經洗掉了 k 位數字
上述步驟結束后我們還需要針對一些情況欄位外的處理：
- 如果我們洗掉了 m 個數字且 m<k，我們需要從序列尾部洗掉額外的 k-m 個數字
- 如果最終的數字序列存在前導零，我們要刪去前導零
- 如果最終數字序列為空，我們應該回傳 0
class Solution {
public String removeKdigits(String num, int k) {
Deque<Character> deque = new LinkedList<>();
for(int i = 0; i < num.length(); i++) {
while(!deque.isEmpty() && k > 0 && deque.peekLast() > num.charAt(i)) {
deque.pollLast();
k--;
}
deque.offerLast(num.charAt(i));
}
for(int i = 0; i < k; i++) {
deque.pollLast();
}
StringBuilder str = new StringBuilder();
boolean leadingZero = true;
while(!deque.isEmpty()) {
char digist = deque.pollFirst();
if(leadingZero && digist == '0') {
continue;
}
leadingZero = false;
str.append(digist);
}
return str.length() == 0 ? "0" : str.toString();
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/217326.html
標籤：其他