📘 題目敘述
給定一個整數陣列 nums。
如果某個元素 nums[i] 滿足以下至少一個條件，就算是 valid：
- 它嚴格大於左邊所有元素
- 它嚴格大於右邊所有元素
另外，第一個元素和最後一個元素永遠都算 valid。
請回傳所有 valid 元素，並且保持它們在原陣列中的出現順序。
條件限制
1 <= nums.length <= 1001 <= nums[i] <= 100
🧠 解題思路
我這題就是直接暴力檢查。
因為這題的資料範圍很小，nums.length <= 100，所以我直接對每個中間元素去檢查：
- 左邊是不是全部都比它小
- 右邊是不是全部都比它小
只要符合其中一個，它就是 valid。
而第一個和最後一個元素題目已經保證一定 valid，所以我直接先把第一個放進答案，最後再把最後一個補進去。
所有變數
n：陣列長度ans：最後要回傳的 valid 元素l：記目前這個元素是否大於左邊所有元素r：記目前這個元素是否大於右邊所有元素
🪜 主要流程步驟
1. 先處理長度為 1 的特例
如果陣列只有一個元素，那它同時也是第一個和最後一個元素，所以一定 valid，直接回傳原本的 nums 就可以：
if (n == 1) {
return nums;
}2. 先把第一個元素放進答案
因為題目保證第一個元素永遠 valid，所以我一開始就先把 nums[0] 放進 ans：
vector<int> ans(1, nums[0]);這樣後面只需要專心檢查中間那些元素。
3. 逐個檢查中間元素是否大於左邊全部或右邊全部
對於每個中間位置 i，我都先設兩個布林值：
l：先假設它不一定比左邊全部大r：先假設它不一定比右邊全部大
然後先往左掃：
for (int j = 0; j < i; j++) {
if (nums[j] >= nums[i]) {
break;
}
if (j == i - 1) {
l = true;
}
}接著我再往右掃：如果一路掃到最右邊都沒有遇到大於等於 nums[i] 的數，就表示它大於右邊所有元素，所以把 r 設成 true。
4. 只要符合其中一個條件，就加入答案
當左邊和右邊都檢查完之後，如果：
if (l || r) {
ans.push_back(nums[i]);
}就代表這個元素至少符合題目要求的其中一種 valid 條件，所以把它加入答案。
5. 最後把最後一個元素補進答案
因為題目保證最後一個元素也永遠 valid，所以在所有中間元素都檢查完之後，我再把 nums[n - 1] 放進去：
ans.push_back(nums[n - 1]);最後回傳 ans 就可以。
⏱️ 複雜度
設 n = nums.length。
- 時間複雜度：
O(n^2)，每個中間元素都可能往左和往右各掃一次。 - 空間複雜度：
O(n)，需要用ans來存最後的 valid 元素。
💻 程式碼實作
class Solution {
public:
vector<int> findValidElements(vector<int>& nums) {
int n = nums.size();
if (n == 1) {
return nums;
}
vector<int> ans(1, nums[0]);
for (int i = 1; i < n - 1; i++) {
bool l = false;
bool r = false;
for (int j = 0; j < i; j++) {
if (nums[j] >= nums[i]) {
break;
}
if (j == i - 1) {
l = true;
}
}
for (int j = i + 1; j < n; j++) {
if (nums[j] >= nums[i]) {
break;
}
if (j == n - 1) {
r = true;
}
}
if (l || r) {
ans.push_back(nums[i]);
}
}
ans.push_back(nums[n - 1]);
return ans;
}
};🔗 題目連結
https://leetcode.com/contest/weekly-contest-499/problems/valid-elements-in-an-array/