求去掉一個數的 k 位後可能的最大數

1. 概述

在本教程中，我們將看到不同的演算法，使我們能夠在刪除數字的 k 位元後找到可能的最大數字。

首先，我們來解釋一下問題。然後，我們將看到兩種適合我們需求的不同演算法。最後，我們將討論它們的複雜性。

2. 問題說明

首先，讓我們解釋一下該演算法的目標是什麼。我們想要找出一個數去掉 k 位後可能的最大數。

例如，考慮數字 286281。我們必須刪除的元素數量為 2，因此最大可能的數字將為 8681。假設我們考慮 k 的另一個值，即 2，因此預期輸出將為 88。

3. 使用算術

在本節中，我們將看到邏輯解釋以及時間和空間複雜度。

3.1.邏輯

讓我們看看使用一些算術有助於實現我們目標的邏輯。我們將使用findLargestNumberUsingArithmetic(num, k)方法來實現傳回結果數字的邏輯。

函數findLargestNumberUsingArithmetic(n,k)有兩個參數： n （原始數字）和k （要刪除的位數）：

public static int findLargestNumberUsingArithmetic(int num, int k) {
 //...
 return num;
 }

我們有一個迭代k次的外循環，表示要刪除的位數：

for (int j = 0; j < k; j++) {
 //...
 }

對於每次迭代，它都會進入一個內部循環來刪除每個數字一次。內循環計算去除每個數字一次後形成的數字，並將其與當前最大數字進行比較：

while (num / i > 0) {
 int temp = (num / (i * 10)) * i + (num % i);
 i *= 10;

 result = Math.max(result, temp);
 }
 num = result;

刪除數字後，如果發現更大的數字，則會更新最大數字。

經過k迭代後，它會傳回剩餘的數字，表示刪除k數字後可能的最大數字：

return num;

3.2.時間和空間複雜度

該程式碼在外循環中迭代k迭代。在外循環內部，有一個 while 循環，它迭代num的數字。這個迴圈對num的每個數字執行，大約是以10為底的對數 num次，因為我們在每次迭代中將num除以 10。因此，內循環的時間複雜度為O(K*log 10 N).

我們沒有使用任何額外的空間，因此空間複雜度將為O(1).

4. 使用堆疊

在本節中，我們將看到一種更優化的方法來提高複雜性。

3.1.邏輯

該方法涉及使用堆疊來追蹤數字的數字，同時確保結果數字最大化。

我們將使用findLargestNumberUsingStack(num, k)方法來實現傳回結果數字的邏輯。

函數findLargestNumberUsingStack(num,k)有兩個參數： num （原始數字）和k （要刪除的位數）。

首先將數字num轉換為字元數組或字串以迭代其數字：

String numStr = Integer.toString(num);
 int length = numStr.length();

如果要刪除的位數與輸入數字的長度相同，我們必須傳回 0：

if (k == length) return 0;

否則，初始化一個空堆疊來儲存數字：

Stack<Character> stack = new Stack<>();

現在，迭代數字num的每個數字並按照以下步驟操作：

• 當堆疊不為空時，目前數字大於棧頂元素，且要移除的剩餘數字個數（ K ）大於0，從堆疊中彈出元素
• 將當前數字壓入堆疊

for (int i = 0; i < length; i++) {
 char digit = numStr.charAt(i);
 while (k > 0 && !stack.isEmpty() && stack.peek() < digit) {
 stack.pop();
 k--;
 }
 stack.push(digit);
 }

如果還有剩餘的數字需要移除（ K ），則從堆疊中彈出元素以滿足條件：

while (k > 0) {
 stack.pop();
 k--;
 }

最後，從堆疊中剩餘的數字中建構最大的數字並傳回結果：

while (!stack.isEmpty()) {
 result.insert(0, stack.pop());
 }
 return Integer.parseInt(result.toString());

4.2.時間和空間複雜度

此演算法對數字的每個數字進行一次迭代，在循環內執行恆定時間操作。因此，時間複雜度將為O(N).

所需的空間主要由用於儲存數字位數的堆疊決定。因此，空間複雜度將為O(N).

5. 結論

在本文中，我們研究了在刪除數字的 k 位後找到可能的最大數字的演算法。我們已經了解瞭如何透過兩種方式實現這一點：算術和堆疊。我們還討論了兩種演算法的時間和空間複雜度，使我們能夠根據需要明智地選擇一種演算法。

與往常一樣，本文中顯示的完整程式碼範例可以在 GitHub 上找到。