LeetCode 376. Wiggle Subsequence (贪心)

Bertha 。 2023-05-30 10:46 24阅读 0赞

题目意思：

例如， \[1,7,4,9,2,5\] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, \[1,4,7,2,5\] 和 \[1,7,4,5,5\] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，返回子序列的长度

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70 1][]

贪心思路：

将两两之间的差值算出来存起来，遍历差值，符合条件入栈，不符合往下找知道符合的数入栈，最终返回栈的长度+1  
注意边界判断，比如空数组

代码：

class Solution {
    public:
        int wiggleMaxLength(vector<int>& nums) {
            vector<int > tmp;
            stack<int > s;
            //贪心思路：将两两之间的差值算出来存起来，遍历差值，符合条件入栈，不符合往下找知道符合的数入栈，最终返回栈的长度+1
            //注意边界判断，比如空数组
            for(int i = 1; i < nums.size(); i++){
                tmp.push_back(nums[i] - nums[i-1]);
            }
            if(tmp.size()){
                //两个数差值为0不可
                if(tmp[0] != 0) s.push(tmp[0]);
            }
            for(int i = 1; i < tmp.size(); i++){
                //避免差值都是零导致空栈越界情况
                if(tmp[i] != 0 && !s.size()){
                    s.push(tmp[i]);
                }else if(tmp[i] != 0 && s.top() * tmp[i] < 0){ //互异
                    s.push(tmp[i]);
                }
            }
            //判断空数组情况
            if(s.size() == 0){
                if(nums.size() == 0) return 0;
                else return 1;
            }else return s.size() + 1;
        }
    };

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70 2][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191109180535842.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191109180605942.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20191109180759111.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5,size_16,color_FFFFFF,t_70