📘 題目敘述
給定一個 bitonic array nums。
請把陣列分成兩部分：
- 遞增部分：從索引
0到 peak element，包含 peak - 遞減部分：從 peak element 到索引
n - 1，包含 peak
注意，peak element 會同時屬於這兩部分。
請回傳：
0：如果遞增部分的總和比較大1：如果遞減部分的總和比較大-1：如果兩部分總和一樣
bitonic array 的意思是：
- 先嚴格遞增
- 到某個唯一 peak 之後再嚴格遞減
條件限制
3 <= n == nums.length <= 10^51 <= nums[i] <= 10^9nums保證是 bitonic array
🧠 解題思路
我這題的想法是直接一邊掃陣列，一邊把遞增部分和遞減部分的和分開累加。
因為題目保證整個陣列是 bitonic，所以走訪時只會有兩種情況：
- 還在遞增段
- 已經進入遞減段
我用 now 記前一個數字。
如果目前數字比 now 大，代表還在遞增段，就把它加到 l。
如果目前數字沒有比 now 大，代表已經開始往下降了，這時就把前一個 peak 或遞減段的數字加到 r。
最後再把最後一個元素補進 r，因為在我的寫法裡，遞減段是在遇到下降時加前一個數，所以最後一個數字要另外補一次。
所有變數
l：遞增部分的總和r：遞減部分的總和now：目前前一個數字，用來判斷現在是在遞增還是遞減
🪜 主要流程步驟
1. 先準備兩部分的總和和前一個數字
我先開兩個 long long 變數 l 和 r，分別記錄遞增部分與遞減部分的總和。
另外再開一個 now，用來記目前前一個數字。
因為題目中的數值和陣列長度都不小，所以總和用 long long 比較安全。
2. 從左到右掃陣列，判斷目前是在遞增段還是遞減段
我直接從左到右掃每個數字 i：
for (int i : nums) {
如果目前的 i 比 now 大：
if (now < i) {
l += i;
now = i;
}
就代表目前還在遞增段，所以我把這個數字加到 l，然後更新 now。
這樣一路加下去，peak 也會被算進 l，符合題目定義。
3. 一旦開始下降，就把前一個數字加進遞減部分
如果目前的 i 沒有比 now 大，就表示已經從 peak 開始往下降了：
else {
r += now;
now = i;
}
這裡我不是把目前的 i 加進 r，而是先把前一個 now 加進去。
這樣做的原因是：
- 遇到第一次下降時，前一個
now就是 peak - 題目規定 peak 要同時算在遞增部分和遞減部分裡
- 所以在開始下降的那一刻，我就先把 peak 加進
r
之後每次繼續下降時，也是一樣把前一個數字補進 r。
4. 迴圈結束後，把最後一個元素補進遞減部分
因為我在遞減段的寫法，是每次遇到新數字時，把「前一個數字」加進 r，
所以最後一個元素在迴圈中不會被加進去。
因此最後要手動補上：
r += nums[nums.size() - 1];
這樣整個遞減部分才會完整。
5. 最後比較兩部分總和大小
當 l 和 r 都算完之後，我就直接比較：
- 遞增部分比較大，回傳
0 - 遞減部分比較大，回傳
1 - 一樣大，回傳
-1
⏱️ 複雜度
設 n = nums.length。
- 時間複雜度：
O(n)
我只從左到右掃過陣列一次。 - 空間複雜度：
O(1)
只用了固定數量的變數。
💻 程式碼實作
class Solution {
public:
int compareBitonicSums(vector<int>& nums) {
long long l = 0, r = 0;
int now = 0;
for (int i : nums) {
if (now < i) {
l += i;
now = i;
} else {
r += now;
now = i;
}
}
r += nums[nums.size() - 1];
if (l > r) {
return 0;
} else if (l < r) {
return 1;
}
return -1;
}
};
🔗 題目連結
https://leetcode.com/contest/biweekly-contest-181/problems/compare-sums-of-bitonic-parts/