題目

給定一個整數數組 nums 和一個正整數 k，返回長度為 k 且最具競爭力的 nums 子序列。

數組的子序列是從數組中刪除一些元素（可能不刪除元素）得到的序列。

在子序列 a 和子序列 b 第一個不相同的位置上，如果 a 中的數字小于 b 中對應的數字，那么我們稱子序列 a 比子序列 b（相同長度下）更具競爭力。例如，[1,3,4] 比 [1,3,5] 更具競爭力，在第一個不相同的位置，也就是最后一個位置上，4 小于 5。

示例

示例 1：

輸入：nums = [3,5,2,6], k = 2

輸出：[2,6]

解釋：在所有可能的子序列集合 [{3,5}, {3,2}, {3,6}, {5,2}, {5,6}, {2,6}] 中，[2,6] 最具競爭力。

示例 2：

輸入：nums = [2,4,3,3,5,4,9,6], k = 4

輸出：[2,3,3,4]

提示：

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 109
• 1 <= k <= nums.length

思路

為了找到最具競爭力的子序列，我們可以使用單調棧（Monotonic Stack）的策略。單調棧是一種保持元素順序的棧結構，在這個問題中，我們需要維護一個遞增棧，以確保子序列的最小化競爭力。

主要思路如下：

1. 遍歷數組 nums，并在每一步中確保棧中的元素保持遞增順序。
2. 如果當前元素比棧頂元素小，并且棧中的元素數目加上剩余的元素數目大于 k，則彈出棧頂元素。
3. 將當前元素入棧，前提是棧的大小小于 k。

mostCompetitive函數

int* mostCompetitive(int* nums, int numsSize, int k, int* returnSize) {*returnSize = k;int* res = (int*)malloc(sizeof(int) * k);int top = -1;  // 棧頂指針，表示當前子序列的最后一個元素的位置for (int i = 0; i < numsSize; i++) {// 如果當前元素比棧頂元素小，并且棧中元素數目加上剩余的元素數目大于k，則彈出棧頂元素while (top >= 0 && nums[i] < res[top] && top + numsSize - i > k - 1) {top--;}// 如果當前棧的大小小于k，則將當前元素入棧if (top < k - 1) {res[++top] = nums[i];}}return res;
}

returnSize 用于記錄返回數組的大小，并將其設置為 k。
為存儲最終結果的數組 res 分配了 k 個整數的內存空間。
top 初始化為 -1，表示棧為空，后續將用于指示棧頂元素的位置。

時間復雜度分析

• for 循環: 該循環遍歷了整個輸入數組 nums，時間復雜度為 O(n)，其中 n 是數組 nums 的長度。

• while 循環: 在每次遍歷中，while 循環最多執行棧中元素的數量（最多 k 次），因為每次循環都可能將棧頂元素彈出，最多進行 k 次操作。在最壞情況下，每個元素都需要進棧或出棧一次，所以 while 循環的總體時間復雜度為 O(n)。

綜上所述，代碼的總體時間復雜度為 O(n)。

空間復雜度分析

• res 數組: 空間復雜度為 O(k)，其中 k 是返回數組的大小，也是最終結果數組的長度。

• top 變量: 使用了一個整數變量來表示棧頂指針，不占用額外的空間，因此空間復雜度為 O(1)。

綜上所述，代碼的總體空間復雜度為 O(k)。

這段代碼的時間復雜度是線性的，因為它只對輸入數組進行了一次線性遍歷。而空間復雜度取決于返回數組的大小 k。

結果