主題
題目連結(jié)：
題目意譯：
你被給定一個索引值從 0 開始的整數(shù)陣列 nums。你被允許根據(jù)你的選擇重新排列 nums 成一個新的陣列 perm。
我們定義 nums 的「傑出度」為索引值 i 的個數(shù)，其中 0 ≦ i < nums.length 且 perm[i] > nums[i]。
回傳你藉由重新排列 nums 得到 perm 之後可以得到的最大傑出度。
限制：
1 ≦ nums.length ≦ 10 ^ 5
0 ≦ nums[i] ≦ 10 ^ 9
範例測資：
範例 1：
輸入： nums = [1,3,5,2,1,3,1]
輸出： 4
解釋： 一個最佳排列為 perm = [2,5,1,3,3,1,1]。
索引值 i = 0 、 1 、 3 和 4 時，perm[i] > nums[i]。因此我們回傳 4。
範例 2：
輸入： nums = [1,2,3,4]
輸出： 3
解釋： 我們可以證明最佳 perm 為 [2,3,4,1]。
索引值 i = 0 、 1 和 2 時，perm[i] > nums[i]。因此我們回傳 3。
解題思維：
可以看到我們先將 nums 中的數(shù)字由大到小排，不會影響所求的索引值個數(shù)（可以看作是最佳解的 perm 綁著 nums 中的數(shù)字一起移動）。
因此現(xiàn)在 nums[0] 是最大值，而 nums[nums.length - 1] 是最小值。
而正因為 nums[0] 是最大值，因此 perm[0] 不可能會大過它。所以 perm[0] 可以是任意數(shù)字，故暫且忽略。
接下來是 nums[1]，如果 nums[1] 跟 nums[0] 數(shù)值一樣，則結(jié)論會跟上面類似；如果不一樣，則我們可以在重新排列時把 perm[1] 設(shè)為 nums[0]（即把 nums[0] 移動到索引值 1 的位置）。因此此時可以讓 perm[1] > nums[1]。
剩下的數(shù)字也是同理。一旦發(fā)現(xiàn)先前「還沒用過」（如同上面的 nums[0] 還沒決定到 perm[1] 之前。因此用完 nums[0] 之後，換 nums[1]）的數(shù)字 nums[j] 大過現(xiàn)在看到的數(shù)字 nums[i]，則將 perm[i] 設(shè)為 perm[j] 便可以使 perm[j] > nums[i]。
也就是說，上述的過程基本上就是從 nums 中大的數(shù)字開始處理。對於每個數(shù)字找盡可能接近且大於它的另一個數(shù)字（如上面的 nums[1] 跟 nums[0]，當(dāng)然實際情況可能不是 nums[0] 去「壓過」 nums[1]）。
過程結(jié)束後，便可以找到最佳的 perm[i] > nums[i] 之?dāng)?shù)量。
為何這樣子是最佳解？在這邊提供一個比較直覺的想法——由於我們一開始由大到小排序了 nums，因此 nums[0] 是最大值。而這代表著它基本上可以拿去放在 perm 中的任意位置來使其大於其他數(shù)字（當(dāng)然，除了數(shù)值相同的以外）。
而在一大堆選擇中，我們應(yīng)該選擇拿 nums[0] 來大過盡可能大的數(shù)字。因為比較小的數(shù)字會有其他數(shù)字（例如說 nums[1]）可以大過它們，而較大的數(shù)字選擇則較少。決定好 nums[0] 之後，就可以當(dāng)作這個數(shù)字不存在。因此此時換成 nums[1] 是最大值，之後便可以重複類似的此結(jié)論直到?jīng)]有可以大過的數(shù)字為止。
正式證明可以用反證法（基本上有點類似上面的直覺想法）來證，不過在此省略。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
