【贪心、DP、线段树优化】Leetcode 376. 摆动序列-EW帮帮网

贪心算法：选 “关键转折点”

初始状态：把数组第一个元素当作起点，此时前一个差值符号设为平坡（即差值为0）。
遍历数组：从第二个元素开始，依次计算当前元素和前一个元素的差值。
差值符号判断：
- 差值大于0：要是之前的差值是小于等于0（平坡或者下降状态），那就说明找到了一个从下降到上升的摆动点，更新最大摆动点数，同时把前一个差值符号标记为上升（大于0）。
- 差值小于0：若之前的差值是大于等于0（平坡或者上升状态），表明找到了一个从上升到下降的摆动点，更新最大摆动点数，并且把前一个差值符号标记为下降（小于0）。
- 差值等于0：这种情况就是遇到了平坡，直接跳过，前一个差值符号保持不变。
特殊情况处理：若数组元素数量小于2，直接返回元素数量。

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if (nums.size() < 2) return nums.size();
        int preDiff = 0, curDiff = 0;
        int res = 1; // 至少有一个元素
        for (int i = 1; i < nums.size(); ++i) {
            curDiff = nums[i] - nums[i - 1];
            // 前一个差为0（初始或平坡） 或者 当前差与前一个差符号不同
            if ((preDiff >= 0 && curDiff < 0) || (preDiff <= 0 && curDiff > 0)) { 
                res++;
                preDiff = curDiff; // 更新前一个差
            }
        }
        return res;
    }
};

动态规划：维护 “上升、下降” 状态

up[i]记录的是以nums[i]结尾且最后一步为上升的最长摆动子序列长度，down[i]记录的是以nums[i]结尾且最后一步为下降的最长摆动子序列长度。在遍历数组的过程中，依据当前元素与前一个元素的大小关系，对这两个数组进行动态更新，最终取二者的最大值。

数组初始化：up和down数组的所有元素都初始化为1。这是因为每个单独的元素都能构成一个长度为1的摆动序列。
遍历数组：从第二个元素开始遍历数组，对于每个元素nums[i]：
- 若当前元素大于前一个元素（即nums[i] > nums[i-1]）：
  - 对于up[i]，由于当前是上升趋势，它的值可以由前一个下降状态转移过来，即up[i] = down[i-1] + 1。
  - 而down[i]保持前一个下降状态的值不变，即down[i] = down[i-1]。
- 若当前元素小于前一个元素（即nums[i] < nums[i-1]）：
  - 对于down[i]，因为当前是下降趋势，它的值可以由前一个上升状态转移过来，即down[i] = up[i-1] + 1。
  - up[i]则保持前一个上升状态的值不变，即up[i] = up[i-1]。
- 若当前元素等于前一个元素（即nums[i] = nums[i-1]）：
  - 这种情况下没有形成摆动，所以up[i]和down[i]都保持前一个状态的值不变，即up[i] = up[i-1]，down[i] = down[i-1]。
结果获取：遍历结束后，up和down数组的最后一个元素分别代表以最后一个元素结尾的上升和下降摆动序列的最大长度，取这两个值中的较大值作为最终结果。

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();
        if (n < 2) return n;
        vector<int> up(n, 1), down(n, 1);
        for (int i = 1; i < n; ++i) {
            if (nums[i] > nums[i - 1]) {
                up[i] = down[i - 1] + 1;
                down[i] = down[i - 1];
            } else if (nums[i] < nums[i - 1]) {
                down[i] = up[i - 1] + 1;
                up[i] = up[i - 1];
            } else {
                up[i] = up[i - 1];
                down[i] = down[i - 1];
            }
        }
        return max(up[n - 1], down[n - 1]);
    }
};

线段树优化动态规划

Node结构体：
- up_max：表示区间内以任意位置结尾且最后一步为上升的最长摆动子序列长度。
- down_max：同理，表示最后一步为下降的最长长度。
SegmentTree类：
- build：递归构建线段树，每个节点维护对应区间的up_max和down_max。
- queryUp/queryDown：查询区间[0, idx]内的最大up/down值，用于动态规划状态转移。
- update：更新指定位置的up和down值，并递归更新父节点。
Solution类：
- wiggleMaxLength：主函数，使用线段树优化的动态规划计算最长摆动序列长度。
- 通过线段树快速查询前缀最大值，实现O(nlogn)时间复杂度。

时间复杂度：O(nlogn)，每次查询和更新操作均为O(logn)。
空间复杂度：O(n)，主要用于存储线段树数组。

#include <vector>
#include <algorithm>
using namespace std;

// 线段树节点结构，维护区间内的up和down状态最大值
struct Node {
    int up_max;     // 区间内以任意位置结尾且最后一步为上升的最长摆动子序列长度
    int down_max;   // 区间内以任意位置结尾且最后一步为下降的最长摆动子序列长度
    Node() : up_max(1), down_max(1) {}  // 默认构造函数，初始值为1（单个元素的情况）
};

class SegmentTree {
private:
    vector<Node> tree;  // 线段树数组
    int n;              // 原始数组大小
    
    // 递归构建线段树
    void build(int node, int start, int end) {
        if (start == end) {
            // 叶子节点，初始值为1
            tree[node] = Node();
            return;
        }
        int mid = (start + end) / 2;
        build(2*node+1, start, mid);      // 构建左子树
        build(2*node+2, mid+1, end);      // 构建右子树
        // 父节点的up_max和down_max取左右子树的最大值
        tree[node].up_max = max(tree[2*node+1].up_max, tree[2*node+2].up_max);
        tree[node].down_max = max(tree[2*node+1].down_max, tree[2*node+2].down_max);
    }
    
    // 查询区间[0, idx]内的up_max
    int queryUp(int node, int start, int end, int idx) {
        if (end <= idx) return tree[node].up_max;  // 当前区间完全在查询范围内
        if (start > idx) return 0;                 // 当前区间完全不在查询范围内
        int mid = (start + end) / 2;
        // 递归查询左子树和右子树并取最大值
        return max(queryUp(2*node+1, start, mid, idx), 
                   queryUp(2*node+2, mid+1, end, idx));
    }
    
    // 查询区间[0, idx]内的down_max
    int queryDown(int node, int start, int end, int idx) {
        if (end <= idx) return tree[node].down_max;  // 当前区间完全在查询范围内
        if (start > idx) return 0;                   // 当前区间完全不在查询范围内
        int mid = (start + end) / 2;
        // 递归查询左子树和右子树并取最大值
        return max(queryDown(2*node+1, start, mid, idx), 
                   queryDown(2*node+2, mid+1, end, idx));
    }
    
    // 更新位置pos的up和down值
    void update(int node, int start, int end, int pos, int up_val, int down_val) {
        if (start == end) {
            // 找到目标叶子节点，更新up和down值
            tree[node].up_max = up_val;
            tree[node].down_max = down_val;
            return;
        }
        int mid = (start + end) / 2;
        if (pos <= mid)
            update(2*node+1, start, mid, pos, up_val, down_val);  // 更新左子树
        else
            update(2*node+2, mid+1, end, pos, up_val, down_val);  // 更新右子树
        // 更新父节点的up_max和down_max
        tree[node].up_max = max(tree[2*node+1].up_max, tree[2*node+2].up_max);
        tree[node].down_max = max(tree[2*node+1].down_max, tree[2*node+2].down_max);
    }
    
public:
    // 构造函数，初始化线段树
    SegmentTree(int size) {
        n = size;
        tree.resize(4*n);  // 线段树数组大小通常为4倍原始数组大小
        build(0, 0, n-1);  // 从根节点开始构建线段树
    }
    
    // 对外接口：查询前idx个位置中的up_max
    int queryUp(int idx) {
        return queryUp(0, 0, n-1, idx);
    }
    
    // 对外接口：查询前idx个位置中的down_max
    int queryDown(int idx) {
        return queryDown(0, 0, n-1, idx);
    }
    
    // 对外接口：更新位置pos的up和down值
    void update(int pos, int up_val, int down_val) {
        update(0, 0, n-1, pos, up_val, down_val);
    }
};

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();
        if (n < 2) return n;  // 边界情况处理
        
        SegmentTree st(n);  // 初始化线段树
        
        // 从第二个元素开始遍历数组
        for (int i = 1; i < n; ++i) {
            // 查询前i-1个位置中的up和down最大值
            int pre_up = st.queryUp(i - 1);
            int pre_down = st.queryDown(i - 1);
            
            int cur_up = 1, cur_down = 1;  // 当前位置的初始值
            
            // 根据当前元素与前一个元素的关系更新cur_up和cur_down
            if (nums[i] > nums[i - 1]) {
                cur_up = pre_down + 1;  // 上升状态可以由前一个下降状态转移而来
                cur_down = pre_down;    // 下降状态保持不变
            } else if (nums[i] < nums[i - 1]) {
                cur_down = pre_up + 1;  // 下降状态可以由前一个上升状态转移而来
                cur_up = pre_up;        // 上升状态保持不变
            } else {
                // 相等时不形成摆动，保持前一个状态
                cur_up = pre_up;
                cur_down = pre_down;
            }
            
            // 更新线段树中当前位置的up和down值
            st.update(i, cur_up, cur_down);
        }
        
        // 返回整个数组中的最大摆动长度
        return max(st.queryUp(n - 1), st.queryDown(n - 1));
    }
};

【贪心、DP、线段树优化】Leetcode 376. 摆动序列

贪心算法：选 “关键转折点”

动态规划：维护 “上升、下降” 状态

线段树优化动态规划

网站公告

今日签到

热门文章

最新发布