📘 題目敘述
你會得到一個整數陣列 nums。
如果一段子陣列 nums[l..r] 滿足以下其中一種形式，則稱它為 alternating：
nums[l] < nums[l+1] > nums[l+2] < nums[l+3] > ...nums[l] > nums[l+1] < nums[l+2] > nums[l+3] < ...
也就是相鄰元素之間的比較符號會「嚴格交錯」出現（><><… 或 <><>…）。
你最多可以從 nums 中移除一個元素（也可以不移除），然後從剩下的陣列中選一段 alternating 的子陣列。
請回傳你能選到的 alternating 子陣列的最大長度。
子陣列是連續且非空的序列。長度為 1 的子陣列也視為 alternating。
條件限制
2 <= nums.length <= 10^51 <= nums[i] <= 10^5
🧠 解題思路
這題我用 DP 逐步掃過陣列，維護「以 i 結尾」時，能形成的 alternating 子陣列最長長度。
alternating 的關鍵在於：最後一次相鄰比較是「變大」或「變小」，會決定下一步能不能接上去。所以我把狀態分成兩種結尾：
b：最後一段比較是「變大」（前一個 < 目前）s：最後一段比較是「變小」（前一個 > 目前）
再加上題目允許「最多刪掉一個元素」，所以每種結尾各分成兩層：
0：還沒有刪元素1：已經刪掉過一個元素
因此總共有四個核心 DP 狀態（都代表「以 nums[i] 結尾」的最長長度）：
b0, s0：沒有刪元素的情況下，以 i 結尾，最後比較為變大/變小b1, s1：已經刪過一個元素的情況下，以 i 結尾，最後比較為變大/變小
更新時分兩段想：
第一段是正常接 nums[i-1] 到 nums[i]：
- 如果
nums[i-1] < nums[i]，代表最後比較是變大，所以新的b0只能從舊的s0接過來（交錯），新的b1也類似，但可以從s1接，或是用「這一次才開始使用刪除」的情況去取最大 - 如果
nums[i-1] > nums[i]，則對稱地更新s0, s1 - 如果相等，因為要求嚴格不等，這一段就不能延長，相關狀態重置成 1
第二段是處理「刪掉 nums[i-1]」的情況：
- 也就是把
nums[i-2]直接接到nums[i]來判斷能不能形成交錯 - 這會用到「i-2 結尾且未刪除」的狀態，所以我額外用
b0p, s0p暫存上一輪之前的b0, s0 - 如果
nums[i-2] < nums[i]，代表這一步形成變大，則可以用s0p + 1去更新b1 - 如果
nums[i-2] > nums[i]，代表這一步形成變小，則可以用b0p + 1去更新s1
每次更新完 nb0, ns0, nb1, ns1，就把答案用四個狀態取最大即可。整體是 O(n) 掃一次，空間 O(1)。
所有變數
b0, s0：尚未移除元素時，以目前位置結尾的最長長度（最後比較為變大 / 變小）b1, s1：已經移除過一個元素時，以目前位置結尾的最長長度（最後比較為變大 / 變小）b0p, s0p：用來保存「i-2 的 b0 / s0」，處理刪掉nums[i-1]後直接接nums[i-2] -> nums[i]的情況nb0, ns0, nb1, ns1：本輪（更新到 i）計算出的新狀態ans：目前掃描到的位置為止的最大答案
🪜 主要流程步驟
1. 初始化四個 DP 狀態
一開始每個單點子陣列長度都是 1，所以 b0, s0, b1, s1 都從 1 開始，ans = 1。
2. 逐步掃描並做狀態轉移
對每個位置 i（從 1 開始）：
- 先看
nums[i-1]和nums[i]的大小關係，決定這一步是「變大」還是「變小」，並更新nb0/ns0（未刪除）與nb1/ns1（已刪除） - 若
i >= 2，再額外用nums[i-2]與nums[i]嘗試做一次「跳過中間元素」的連接，把「刪掉nums[i-1]」這種情況補進nb1/ns1 - 用更新後的四個狀態更新
ans - 把
b0p/s0p往前推，並把本輪新狀態覆蓋回b0/s0/b1/s1
3. 回傳答案
掃完後回傳 ans。
💻 程式碼實作
class Solution {
public:
int longestAlternating(vector<int>& nums) {
int n = nums.size();
int b0 = 1, s0 = 1; // b是最後是變大，s是最後是變小
int b1 = 1, s1 = 1;
int b0p = 1, s0p = 1; // 用來看i-2的0
int ans = 1;
for (int i = 1; i < n; i++) {
int nb0 = 1, ns0 = 1;
int nb1 = 1, ns1 = 1;
if (nums[i - 1] < nums[i]) {
nb0 = s0 + 1;
nb1 = max(s1 + 1, nb0);
} else if (nums[i - 1] > nums[i]) {
ns0 = b0 + 1;
ns1 = max(b1 + 1, ns0);
} else {
nb0 = ns0 = 1;
nb1 = ns1 = 1;
}
if (i >= 2) {
if (nums[i - 2] < nums[i]) {
nb1 = max(nb1, s0p + 1);
} else if (nums[i - 2] > nums[i]) {
ns1 = max(ns1, b0p + 1);
}
}
ans = max(ans, max(nb0, ns0));
ans = max(ans, max(nb1, ns1));
b0p = b0;
s0p = s0;
b0 = nb0;
s0 = ns0;
b1 = nb1;
s1 = ns1;
}
return ans;
}
};
🔗 題目連結
https://leetcode.com/contest/weekly-contest-487/problems/longest-alternating-subarray-after-removing-at-most-one-element/