前言

題目的鏈接，大家可以先試著去做一下再來看一下思路。179. 最大數 - 力扣（LeetCode）

題目解析

還是老樣子，把題目讀懂，畫出有用信息。

認真看示例，要好好去想一下，特殊示例的情況。

算法原理

字典序

插個小曲，介紹一下字典序。

1. 概念：
   字典序（LexicographicalOrder），也稱為詞典序、字母序或詞典順序，是一種基于字符順序的字符串比較方法。它類似于我們在字典中查找單詞的順序。
2. 字符編碼基礎
   字典序依賴于字符的編碼系統：
   ASCII：‘0’=48, ‘1’=49, …, ‘9’=57, ‘A’=65, ‘B’=66, …, ‘a’=97, ‘b’=98, …
   Unicode：包含更多字符，但數字和字母的順序與ASCII一致。
3. 比較規則
   字典序的核心規則是從左到右逐字符比較：

比較第一個字符： 如果字符不同，則根據字符的編碼值（如ASCII或Unicode）決定順序；編碼值小的字符串排在前面 。
例一： “apple” vs “banana” → “apple” < “banana”（因為 ‘a’<‘b’）；

如果第一個字符相同：比較第二個字符；依此類推，直到找到不同的字符。
例二：“dat” vs “dog” → “dat” < “dog”（因為’a’<‘o’）

所有字符都相同： 較短的字符串排在較長的字符串前面。
例三：“hello” vs “hell” → “hell” <“hello”（相同前綴，較短者優先）

4. 示例解析

數字字符串比較：
“2” vs “10” → “10” < “2”（因為 ‘1’<‘2’）
“30” vs “4” → “30” <“4”（因為 ‘3’<‘4’）
“100” vs “2” → “100” < “2”（因為 ‘1’<‘2’）
混合比較：
“file9” vs “file10” → “file10” < “file9”（因為 ‘1’<‘9’）
“item2” vs “item10” → “item10” < “item2”（因為 ‘1’<‘2’）

5. 在本代碼中的應用
   在largestNumber算法中（largestNumber 算法通常指的是如何將一組非負整數重新排列，使得它們拼接后的數字是最大的。），我們使用字典序比較拼接后的字符串為什么有效呢。

//這行代碼是自定義排序比較邏輯的核心，它決定了兩個字符串在排序時的相對順序。
//如果 s1 + s2 組成的字符串更大，返回 true，表示 s1 應該排在 s2 前面。
//如果 s2 + s1 更大，返回 false，表示 s2 應該排在 s1 前面。
return s1 + s2 > s2 + s1;

長度相等：s1+s2和s2+s1長度相同（len(s1)+len(s2)）
字典序等價數值序：當兩個數字字符串長度相同時，字典序大小關系等同于數值大小關系。

6. 字典序與數值序的區別

比較方式	“2” vs “10”	“30” vs “4”	“100” vs “2”
字典序	“10” < “2”	“30” < “4”	“100” < “2”
數值序	10 > 2	30 > 4	100 > 2

字典序：基于字符編碼從左到右比較.。
數值序：基于實際數值大小比較。

7. 在算法中的重要性

在本問題中，使用字典序比較拼接字符串是高效的，因為：
避免了大數計算（拼接后可能超出整數范圍） 。
利用字符串比較的內置優化。
當長度相同時，保持數值大小關系。

8. 總結

字典序是一種基于字符編碼順序的字符串比較方法：
從左到右逐字符比較。
編碼值小的字符排在前。
相同前綴時較短字符串排在前。
在等長數字字符串比較中等價于數值比較。

代碼示例

class Solution {
public:string largestNumber(vector<int>& nums){//優化一下，把所有的整數轉化為字符串，我們用字典序去比較，比直接轉換整形比較好很多，vector<string> str;for(auto x : nums) str.push_back(to_string(x));//排序，拼接字符串，比較字典序。當兩個數字字符串長度相同時，字典序大小關系等同于數值大小關系。//標準庫的 sort 通常使用快速排序，這類比較排序算法的核心是通過多次比較和交換元素位置來達到有序。sort(str.begin(),str.end(),[](const string &s1, const string &s2){return s1 + s2 > s2 + s1;});//提取結果string ret;for(auto &s : str) ret += s;//特殊情況，數組中全是0不能返回"000..."，應該返回"0"if(ret[0] == '0') return "0";return ret; }
};

策略證明

證明方法：全序關系

全序關系（Total Order）是指在一個集合X上，滿足以下三個條件的二元關系：
完全性：對于集合中的任意兩個元素a和b，要么a ≤ b，要么b ≤ a 。
反對稱性：如果a ≤ b且b ≤ a，則a = b。
傳遞性：如果a ≤ b且b ≤ c，則a ≤ c。
全序關系也稱為線性序或簡單序。一個具有全序關系的集合稱為全序集。
例如，實數集上的小于等于關系（≤）就是一個全序關系，因為任意兩個實數都可以比較大小。

假設定義了集合{a,b,c,d,e,f,g}，我從集合中任意挑選兩個元素，如果這兩個元素在你定義的比較規則下，滿足全序關系的話，我們就說這個集合是可以排序的。
只要滿足下面三個性質，就有全序關系。
1.完全性，2.反對稱性，3.傳遞性

我們接下來就要去證明我們算法原理中的自定義排序是否有效。