给你一个数组 nums ，它包含若干正整数。

一开始分数 score = 0 ，请你按照下面算法求出最后分数：

从数组中选择最小且没有被标记的整数。如果有相等元素，选择下标最小的一个。
将选中的整数加到 score 中。
标记 被选中元素 ，如果有相邻元素，则同时标记 与它相邻的两个元素 。
重复此过程直到数组中所有元素都被标记。

请你返回执行上述算法后最后的分数。

示例 1：

**输入：** nums = [2,1,3,4,5,2]
**输出：** 7
**解释：** 我们按照如下步骤标记元素：
- 1 是最小未标记元素，所以标记它和相邻两个元素：[ _ **2**_ , _ **1**_ , _ **3**_ ,4,5,2] 。
- 2 是最小未标记元素，所以标记它和左边相邻元素：[ _ **2**_ , _ **1**_ , _ **3**_ ,4, _ **5**_ , _ **2**_ ] 。
- 4 是仅剩唯一未标记的元素，所以我们标记它：[ _ **2**_ , _ **1**_ , _ **3**_ , _ **4**_ , _ **5**_ , _ **2**_ ] 。
总得分为 1 + 2 + 4 = 7 。

示例 2：

**输入：** nums = [2,3,5,1,3,2]
**输出：** 5
**解释：** 我们按照如下步骤标记元素：
- 1 是最小未标记元素，所以标记它和相邻两个元素：[2,3, _ **5**_ , _ **1**_ , _ **3**_ ,2] 。
- 2 是最小未标记元素，由于有两个 2 ，我们选择最左边的一个 2 ，也就是下标为 0 处的 2 ，以及它右边相邻的元素：[ _ **2**_ , _ **3**_ , _ **5**_ , _ **1**_ , _ **3**_ ,2] 。
- 2 是仅剩唯一未标记的元素，所以我们标记它：[ _ **2**_ , _ **3**_ , _ **5**_ , _ **1**_ , _ **3**_ , _ **2**_ ] 。
总得分为 1 + 2 + 2 = 5 。

提示：

1 <= nums.length <= 105
1 <= nums[i] <= 106

2593. 标记所有元素后数组的分数 - 第 100 场双周赛

直接模拟

就按题目直接写，唯一的技巧就是把下标和数值并组排序；
至于为什么可行，因为题目 n 才 10^5 ，中等题放放水很正常；

[]class Solution:
    def findScore(self, nums: List[int]) -> int:
        n = len(nums)
        v = [False] * n
        li = sorted((val,i) for i,val in enumerate(nums))
        ans = 0
        for val,i in li:
            if v[i]: continue
            ans += val
            v[i] = True
            if i > 0: v[i - 1] = True
            if i < n - 1: v[i + 1] = True
        return ans

O(n) 贪心 + 反悔

实际这种题如果仔细观察还真有一般性规律可以用；

观察局部 xxx213xxx 可发现，无论前后 xxx 换成什么数字，由于 213 包裹了 1 ，所以 1 怎么都会被选中，2和3怎么都不会被选中，甚至改成 xxx929xxx 也是一样的结论，可以理解为由于中间比两边小，无论如何最后都会选中中间的数字而不会选中两边的数字，顶多两边数字因为有更小的再旁边提前作废，但结果看都是作废，那么局部看这个结构是固定的，不随其他外部数字所改变，很明显我们可以搞类似贪心全选然后反悔之前选择的套路；

我们可以稍微扩展一下这个范围，或者说限制范围，我们就从左到右分析，那么已知之前最优结构的答案是 ans，那么我们当前可以有 3 这种情况分析：

前面一个没有选中，那么当前就是 213 后面的新开始，从新选择；
前面一个选中，当前的更小，那么当前就是 213 的 1 选 1 并反悔之前选的 2；
前面一个选中，当前的更大，那么当前就是 213 的 3 这是作废选项反悔清零；

那么如果想选当前的选择就必须反悔之前的选择，就需要维护一个 backtrack[i - 1] ，表示反悔前一个选择需要回加多少数值，而当前 backtrack[i] 就等于是把当前选中的数值和之前反悔又还原回去；

再分析可以发现不需要使用数组，因为反悔仅用到 backtrack[i - 1] ，直接用变量代替即可；

[]class Solution:
    def findScore(self, nums: List[int]) -> int:
        n = len(nums)
        backtrack = -nums[0]
        ans = nums[0]
        # 前面被选中 backtrack 就不会为 0 ，因为为 0 等于与之前相等，但如果相等肯定是下标小的选中，而下标大的会被抛弃故还是 0 ；
        # 情况一：前面一个没有选中，那么当前就是 213 后面的新开始，从新选择；
        # 情况二：前面一个选中，当前的更小，那么当前就是 213 的 1 选 1 并反悔之前选的 2；
        # 情况三：前面一个选中，当前的更大，那么当前就是 213 的 3 这是作废选项反悔清零；
        for preNum,num in itertools.pairwise(nums):
            if backtrack == 0:
                ans += num
                backtrack = -num
            else:
                if preNum > num:
                    ans += num + backtrack
                    backtrack = - num - backtrack
                else: backtrack = 0
        return ans

[]class Solution {
    public long findScore(int[] nums) {
        final int n = nums.length;
        long ans = nums[0], backtrack = nums[0];
        
        // 前面被选中 backtrack 就不会为 0 ，因为为 0 等于与之前相等，但如果相等肯定是下标小的选中，而下标大的会被抛弃故还是 0 ；
        // 情况一：前面一个没有选中，那么当前就是 213 后面的新开始，从新选择；
        // 情况二：前面一个选中，当前的更小，那么当前就是 213 的 1 选 1 并反悔之前选的 2；
        // 情况三：前面一个选中，当前的更大，那么当前就是 213 的 3 这是作废选项反悔清零；

        for (int i = 1; i < n; i++) {
            if (backtrack == 0) {
                ans += nums[i];
                backtrack = nums[i];
            } else {
                if (nums[i - 1] > nums[i]) {
                    ans += nums[i] - backtrack;
                    backtrack = nums[i] - backtrack;
                } else backtrack = 0;
            }
        }
        return ans;
    }
}

分段统计

这是时候再看看灵神的解，两种做法：从 O(nlogn) 到 O(n) ，如果固定结构的角度理解就好理解多了，实际就是把整一段理解为多个 919 逐一处理，而这个 919 也可以扩展为 9876543219，而因为存在连续连续递减，所以必然是最小的往前选一个隔一个，最后两头都是废弃选项，然后继续处理下一段 919；

这种 3 个指针的处理方式也是很妙；

[]class Solution {
    public long findScore(int[] nums) {
        long ans = 0;
        for (int right = 0, left, mid; right < nums.length; right += 2) {
            left = right;
            while (right + 1 < nums.length && nums[right + 1] < nums[right]) {
                right++;
            }
            for (mid = right; mid >= left; mid -= 2) {
                ans += nums[mid];
            }
        }
        return ans;
    }
}

2593-标记所有元素后数组的分数

直接模拟

O(n) 贪心 + 反悔

分段统计

完