解題說明
Squares of a Sorted Array
題目描述：
給定一個按非遞減順序排列的整數陣列 nums（可能包含負數），返回每個數字的平方值組成的新陣列，且新陣列也按非遞減順序排列。
解題思路： 雙指標法：
由於陣列已排序，平方值最大的元素一定在兩端之一（最大的正數或絕對值最大的負數）。
- 設左指標
lo = 0，右指標hi = n - 1。 - 從結果陣列的尾部開始填入（從大到小）：
- 比較
|nums[lo]|和|nums[hi]|，將較大者的平方放入結果。 - 移動對應指標。
- 比較
- 這樣一次遍歷即可得到有序的平方陣列。
C++ 解法
複雜度分析
時間複雜度：O(n) — 雙指標各移動一次，每個元素恰好處理一次。
空間複雜度：O(n) — 結果陣列（不計入的話為 O(1)）。
虛擬碼
1. Initialize result array of size n.
2. Set lo = 0, hi = n - 1, pos = n - 1.
3. While pos >= 0:
a. If |nums[lo]| >= |nums[hi]|:
result[pos] = nums[lo]^2, increment lo.
b. Else:
result[pos] = nums[hi]^2, decrement hi.
c. Decrement pos.
4. Return result.其他解法
暴力法：O(n log n) 時間。先將所有元素平方，再排序。簡單直接但未利用輸入已排序的性質。
找零點 + 雙向合併：O(n) 時間。先找到正負數的分界點，然後用類似合併排序的方式從中間向兩端合併。邏輯等價於雙指標法但實作稍複雜。
延伸思考
- 為什麼從結果陣列尾部開始填入而非頭部？如果從頭部填入會有什麼困難？
- 如果輸入全為非負數，此演算法是否還需要雙指標？
- 此題的雙指標技巧與合併兩個有序陣列（Merge Sorted Array）有何相似之處？